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

- \(\Theta(n^2)\)
- \(\Theta(n\log n)\)
- \(\Theta(n^{1.5})\)
- \(\Theta(n)\)

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

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

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

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

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

0

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

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?

As we know in insertion sort complexity depend on number of inversions rt?

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)

reference : https://en.wikipedia.org/wiki/Adaptive_sort

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

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

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

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

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**

0 votes

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

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