2.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 | 2.5k views
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.

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) ?
+4

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
+2
@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?
+2
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 .

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 $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 atmost $N$ inversions are there, so we get the best Time complexity :- $\Theta (N+f(N)) = \Theta (N + N) = \Theta (N)$ .

edited by
+1
Excellent explanation 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.