As the question says, how the Inversion is defined .
In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\).
- One important thing to see is Difference between swap and Inversions.
- Swapping is done explicitly by the programmer, hence a explicit feature whereas, Inversion is an implicit feature which is defined in the input .
Ex :- Take the input => $\left \{ 0,1,9,8,10,7,6,11 \right \}$
How many Inversions here : $\left \{ 9,8 \right \}$ , $\left \{ 9,7 \right \}$ , $\left \{ 9,6 \right \}$ ,$\left \{ 8,7 \right \}$ , $\left \{ 8,6 \right \}$ , $\left \{ 10,7 \right \}$, $\left \{ 10,6 \right \}$ and $\left \{ 7,6 \right \}$ . Hence, it is an implicit feature of the input and not any explicit operation done (Swap) .
Actual Time complexity of Insertion Sort is defined as $\Theta \left ( N + f(N) \right )$, where $f\left ( N \right )$ is the total number of Inversions .
Ex :- Again take the input => $\left \{ 0,6,7,8,9,10,1 \right \}$
Here, how many comparisons will be there to place $1$ in the right place ?
- First of all, $1$ is compared with $10$ - Returns True as it is smaller than $10$.
- Then, with $9$ - again True.
- Similar, happens with $6,7,8$ - All return True .
Hence, There $5$ comparisons were the Inversions and $1$ more comparison will be there, in which outer while loop fails .
For, placing $1$ in the right place $\bf{6}$ comparisons are there .
Hence, Total Comparisons in the Insertion sort will be :- Total number of elements for which our while loop fails + Total number of inversions in the input
- Total number of elements for which our while loop fails :- Suppose the input $\left \{ 0,6,7,8,9,10,1 \right \}$. Here, first $0$ will be kept as it is and one while loop fail comparison for each element, hence total comparisons like this :- $\left ( N-1 \right )=O\left ( N \right )$ comparisons.
- Total number of inversions in the input :- Best Case : $0$ and in the Worst Case : $\frac{N\left ( N-1 \right )}{2} = O\left ( N^{2} \right )$
Total Time complexity of insertion sort : $\Theta (N+f(N))$
It is given here that at most $N$ inversions are there, so we get the best Time complexity :- $\Theta (N+f(N)) = \Theta (N + N) = \Theta (N)$ .
Correct Answer: $D$