# GATE2003-62

8.5k views

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

edited
0
what is inversion???????????????????????
0
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.
0

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$

edited
1
Excellent explanation Sir!
0
0
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).
1
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
0

@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.

0

The link mentioned is not working.

https://gateoverflow.in/253812/gatebook-2019-ds3-9
0
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
0
The number of comparisons in insertion sort are O($N^{2}$) then how is the total time complexity O(N)??

1
I think (7,6) should also be an inversion.

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
0
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) ?
13

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.

0
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
6
@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.
0
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?
4
yes, exactly. This question is about analysing the complexity of insertion sort.
3
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)

http://www.geeksforgeeks.org/time-complexity-insertion-sort-inversions
0
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)
0
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 .

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.

1 vote
You can learn this point:-

Insertion sort complexity is

(N+ no. of inversion).
1 vote

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

0

@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?

1 vote

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

inputs are restricted to permutations of $1...n$ with at most $n$ inversions

so if we take input as $n,1,2….n-1,n-2$

here no. of inversions is$n$

e.g. if n=9

$9,1,2,3,4,5,6,8,7$

inversions are

$(9,1)(9,2)(9,3)(9,4)(9,5)(9,6)(9,8)(9,7)(8,7) i.e. 9$

so worst case input according to question is  $n,1,2….n-1,n-2$

this will take O(N) time to sort using insertion sort as except n & n-2 all elements are sorted
ago

## Related questions

1
7.3k views
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$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$? $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{4}$ $\frac{n(n+1)}{4}$ $2n[\log_2n]$
The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will remain $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k <= n; k++) A[k] ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex ... longest path length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges