GATE CSE 2003 | Question: 62

Question

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?

• A. $\Theta(n^2)$
• B. $\Theta(n\log n)$
• C. $\Theta(n^{1.5})$
• D. $\Theta(n)$

Comments

Insertion sort time complexity = No. of comparisons + No. of swaps

take an example,

2 3 4 5 6 7 8 . ----------------------n 1   (total n elements and n-1 inversions)

T.C. = no. of comparisons + no. of swaps

        = ((n-2) + (n-1)) + (n-1)

       = ( 3, 4, 5 …. n every need 1 comparison + 1 alone need (n-1) comparisons) + for 1 swaps

       = 3(n-1)-1

       = $\Theta (n)$

---

Thank You for the explanation

---

@ASNR1010 Really beautiful eg and explanation. Thanks

Answer 1

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

 

Comments

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

Answer 2

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

Answer 3

You can learn this point:-

Insertion sort complexity is

(N+ no. of inversion).

Answer 4

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