The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+33 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)\)

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

+34 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

+10

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

+3

@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

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

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users