edited by
19,512 views
70 votes
70 votes

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?

  1. $\Theta(n^2)$
  2. $\Theta(n\log n)$
  3. $\Theta(n^{1.5})$
  4. $\Theta(n)$
edited by

9 Answers

2 votes
2 votes

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

 

2 votes
2 votes

In insertion sort, whenever we swap two values, some inversions are destroyed, also no new inversions are created, since smaller element comes at lower index in array. The no. of inversions destroyed is exactly the number of comparisons done before that swapping. So for every comparison, there is an inversion destroyed. Since there are at most n inversions initially, so in at most n comparisons, array will be sorted. So worst time complexity is Θ(n). So option (D) is correct.

 

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2003.html

0 votes
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
Answer:

Related questions