GATE CS 2003 Q62 — Searching, Sorting, Hashing

The run time of the Insertion Sort algorithm is closely tied to the number of inversions in the input array.

Let $n$ be the number of elements in the array and $I$ be the number of inversions.

• In Insertion Sort, each swap of adjacent elements reduces the number of inversions by exactly $1$. Therefore, the total number of shifts/swaps performed is exactly equal to the number of inversions $I$.
• For each of the $n$ elements, the algorithm performs at least one comparison to determine its correct position (even if no swap is needed). Thus, the total number of comparisons is at most $I + n$.

Consequently, the total time complexity $T(n)$ of Insertion Sort is given by:

Given that the input permutations are restricted to at most $n$ inversions (i.e., $I \le n$), we can substitute this upper bound into the complexity relation:

Thus, the worst-case time complexity under this restriction is $\Theta(n)$.