¿Complejidad temporal del ordenamiento por inserción cuando hay inversiones O(n)?

¿Qué es una inversión?
Dada una array arr[], un par arr[i] y arr[j] forma una inversión si arr[i] < arr[j] e i > j. Por ejemplo, la array {1, 3, 2, 5} tiene una inversión (3, 2) y la array {5, 4, 3} tiene inversiones (5, 4), (5, 3) y (4, 3) . Hemos discutido un algoritmo basado en ordenación por combinación para contar inversiones

¿Cuál es la complejidad temporal de la ordenación por inserción cuando hay inversiones O(n)?
Considere la siguiente función de clasificación por inserción.

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
   
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

Si observamos más de cerca el código de clasificación de inserción, podemos notar que cada iteración del ciclo while reduce una inversión. El ciclo while se ejecuta solo si i > j y arr[i] < arr[j]. Por lo tanto, el número total de iteraciones del bucle while (para todos los valores de i) es el mismo que el número de inversiones. Por lo tanto, la complejidad temporal general del ordenamiento por inserción es O(n + f(n)) donde f(n) es el recuento de inversión. Si el recuento de inversiones es O(n), entonces la complejidad temporal de la ordenación por inserción es O(n). En el peor de los casos, puede haber n*(n-1)/2 inversiones. El peor de los casos ocurre cuando la array se ordena en orden inverso. Entonces, la complejidad de tiempo del peor caso del ordenamiento por inserción es O(n ² ).

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.