edited by
19,527 views
70 votes
70 votes

In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j.$

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most $n$ inversions?

  1. $\Theta(n^2)$
  2. $\Theta(n\log n)$
  3. $\Theta(n^{1.5})$
  4. $\Theta(n)$
edited by

9 Answers

Best answer
81 votes
81 votes

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$

edited by
41 votes
41 votes

ANSWER: D. $\Theta(n)$

REASON:

Count of number of times the inner loop of insertion sort executes is actually equal to number of inversions in input permutation $a_1,a_2,\dots a_n$. Since for each value of $i = 1... n$, $j$ take the value $1... i-1$, which means for every $j<i$ it checks if $a[j] > a[i]$.

In any given permutation, maximum number of inversions possible is $n(n-1)/2$ which is $O(n^2)$. It is the case where the array is sorted in reverse order. Therefore, to resolve all inversions i.e., worst case time complexity of insertion sort is $\Theta(n^2)$.

However, as per the question the number of inversion in input array is restricted to $n$. The worst case time complexity of insertion sort reduces to $\Theta(n)$. 


INSERTION SORT ALGORITHM (for reference)

edited by
5 votes
5 votes

Time complexity of insertion sort is: $O(n + i)$ where $i$ is the number of inversions.

In the worst case, there are $n(n-1)/2=O(n^2)$ inversions, and hence the Time Complexity of Insertion Sort degrades to $O(n+n^2)=O(n^2)$.

 

Here, in the worst case we're restricted to $n$ inversions, so Time Complexity = $\theta(n+n)=\theta(n)$

Option D

Answer:

Related questions