The Gateway to Computer Science Excellence
+40 votes

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\).

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)\)
in Algorithms by Veteran (105k points)
edited by | 5.7k views
what is inversion???????????????????????
Let A[1..N] be an array of distinct elements.
If i < j and A[i]>A[j] the pair i,j is known as inversion of the Array.

6 Answers

+39 votes
Best answer

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 \}$ and $\left \{ 10,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$

by Veteran (50.9k points)
edited by
Excellent explanation Sir!
In worst case when the array is sorted in descending order the complexity would be O(n^2). But since its restricted to n inversions, so the complexity would be now O(n).
Restriction on inversión to n mean array is almost sorted in increasing order.let us take an example

5 1 2 3 4

Here insertion sort will stop after first pass by making array sorted and inversion will be number of swap

@Kapil sir you saved my many hours the key is just read the question carefully : they explicit mentioned that number of inversions are restricted up to n then why we considering O(n^2) case it should be done only in O(n) time. 



The link mentioned is not working.
could u please elaborate more on "Actual Time complexity of Insertion Sort is defined as Θ(N+f(N))Θ(N+f(N)), where f(N)f(N) is the total number of Inversions ." ??? I didn't get this point
+35 votes

ANSWER: D. $\Theta(n)$


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)$. 


by Active (4.7k points)
edited by
array could be 5,4,3,2,1

in best case of insertion sort will take O(n)

But how in worst case O(n) ?

If the array elements are 5,4,3,2,1..then number of inversion equals 10 which is twice the size of array. Question restrict the number of inversions to $n$.

Best case of insertion sort means that the inner while loop was never executed at all. That will happen when there is no inversion at all (array is sorted). Since, the outer loop has traversed the element of array once therefore the complexity is O(n) in best case.

However in this particular case we should not make a claim that the inner loop will not be executed. Actually it will execute, but only O(n) time in total (not just for some iteration of outer loop). So in worst case i.e., irrespective of whatever is the given permutation, as long as number of inversion in that permutation is $n$ insertion sort will sort that array in O(n). That actually the claim here.

means in 5,4,3,2,1

4 inversion it will be 1,5,4,3,2

then 1 inversion 1,5,4,2,3....We have to stop here
@srestha inversions are not operations (swaps) done by us- it is a property of the input. 5,4,3,2,1 has 4+3+2+1 = 10 inversions.
ok , so here atmost n inversion . that is why complexity O(n).rt?

As we know in insertion sort complexity depend on number of inversions rt?
yes, exactly. This question is about analysing the complexity of insertion sort.
Outer loop executes n times. Inner loop will also be executed n times as there are n inversions.

So complexity will be $\Theta$ (n + n) . So $\Theta$ (n)

reference :
please add that running time is Θ(n+d), where n we get from outer loop and d is the  number of inversion.

here number of inversion=n

so time complexity=Θ(n+n)= Θ(n)
inversions are not operations (swaps) done by us- it is a property of the input. 5,4,3,2,1 has 4+3+2+1 = 10 inversions.
i can't get it sir .
+10 votes

Ans is D: ⊝(n), 

Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.


by Active (3k points)
+1 vote
You can learn this point:-

Insertion sort complexity is

(N+ no. of inversion).
by (213 points)
0 votes

Just take a simple case and examine:

Usually, the worst case corresponds to whenever input is in decreasing order, so

let Input = 5,4,3,2,1

Now, we need to make sure the inversion property applies i.e. n=5 inversions are only possible

For the given I, there's 10 inversions. With the number 5, there's 4 inversions - <5,4> , <5,3>, <5,2>, <5,1>. We just need 1 more. By rearranging, let I = 5,1,2,4,3. Now there's 5 inversions. We have a perfect example close to worst case.

Now apply the insertion sort Algo to I.


Iteration(i,j)  Input

0,0 - 5,1,2,4,3

1,0 - 1,5,2,4,3

2,0 - 1,2,5,4,3

3,0 - 1,2,4,5,3

4,0 - 1,2,4,3,5

4,1 - 1,2,3,4,5


Total Iterations = 5. Therefore Theta(n), option D


by (275 points)
0 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

by Loyal (6.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,279 answers
104,839 users