GATE CSE 2003 | Question: 62

Question

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?

• A. $\Theta(n^2)$
• B. $\Theta(n\log n)$
• C. $\Theta(n^{1.5})$
• D. $\Theta(n)$

Comments

Thank You for the explanation

---

@ASNR1010 Really beautiful eg and explanation. Thanks

---

What is inversion: Pair of elements that are out of order

i.e in array 2 3 4 1 --- we see that (2,1) are out of order, (3,1) and (4,1) is also out of order. So, number of inversions are 3 ---- (Important)
Now they say in the question that there is an array of 'n' elements in any arbitary order and they have given that the number of inversion in the array is 'n' 

Consider the array 2 3 4 1 --- 
Using insertion sort,
From 3, 1 comparison, 0 swaps
From 4, 1 comparision, 0 swaps
From 1, 3 comparisions, 3 swaps

From this, we see that number of inversions = No. of swaps made

So, Time complexity = O( number of swaps) = O(n) 

But, there is one case to handle before finalizing the Time complexity

What if we have a sorted array as an input, Lets say 1 2 3 4
Then if we run Insertion sort then the number of swaps are 0 but the comparisons will still be n-1(We still have to compare every element) ~ O(n)

So, we write the Time complexity of Insertion sort as, O(number of comparision + number of swaps)
In this question, we had O( n + n) = O(n)

 

Answer 1

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$

Comments

@hollow_mind

if the array is already in descending order then it will take O(n^2) to sort in ascending order due to n(n-1)/2 inversions. 

---

nice explaination

---

Thank you so much for explaining the whole concept of what inversion is along side explaining the answer!

Answer 2

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)

Comments

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 : https://en.wikipedia.org/wiki/Adaptive_sort

http://www.geeksforgeeks.org/time-complexity-insertion-sort-inversions

---

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.
@Arjun
i can't get it sir .

Answer 3

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.

Read more at http://geeksquiz.com/gate-gate-cs-2003-question-62/

Answer 4

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 5

You can learn this point:-

Insertion sort complexity is

(N+ no. of inversion).

Answer 6

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

 

Comments

@arjuno

can you explain little more how you find total iteration and what is that 1,0  2,0 ....4,0  4,1  stands for?