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

Looking at the code of insertion sort we can see that we require one comparison for all ‘n’ elements initially. (yes for the first element we don’t need this, but let us ignore it.). Therefore ‘n’ comparisons.

Then for each swap(= number of inversions, let it be ‘d’), there will be one comparison each to check whether we need to swap or not. Therefore ‘d’ more comparisons.

Obviously ‘d’ swaps for ‘d’ inversions. Therefore O(n+d+d) = O(n+d).

Here d=n, therefore O(n).