What is an Inversion ??

Question

47. An array ' $A$ ' contain ' $I$ ' number of Inversions then what is the Time Complexity of insertion sort algorithm to sort ' $n$ ' element of array ' $A$ '?

• A. $\mathrm{O}(\mathrm{n}+\mathrm{I})$
  
• B. $\mathrm{O}\left(\mathrm{n}^{2}+\mathrm{I}\right)$
  
• C. $\mathrm{O}\left(\mathrm{n}^{3}+\mathrm{I}\right)$
  
• D. $\mathrm{O}\left(\mathrm{n}^{4}+\mathrm{I}\right)$

Comments

Let A[1....n] be an array of n distinct numbers . if i<j and A[i] > A[j] then the pair (i ,j) is called an inversion pair of A.

---

https://gateoverflow.in/4550/time-complexity

https://gateoverflow.in/949/gate2003_61-62

Answer 1

If the given array is already sorted and maximum n inversion is possible then insertion sort gives best case for that array because array is already sorted.i.e O(n)

e.g. = 10 20 30 40 50 60 1 : 
here 6 inversion and array is almost sorted so it will take 6 comparison and 6 swaps 

if array is of n element and 1 element is not sorted then :      O(n) for searching the position 
                                                                                         n swap 
                                                                                         O(2n) 
for n element n*2n = O(n²)

So we can say if in array there are I inversion is there then Time Complexity = O(n + I) 
                                                                                         O(n) for best case for I= n 
                                                                                         O(n2) for worst case if I is more than n
​optiion A         

Answer 2

Insersion sort will take O( n²  )  using merge sort complexity will be O(nlogn)