GATE CS Applied Course

## ALGORITHM

0

In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. 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) ? (n2) B) ? (n log n) C) ? (n1.5) D) ? (n)

1

##### Arnab Das Posted on Sep 13, 2019 08:08 PM

At every step of Insertion algorithm, to find the proper location of the current element(a[j]) in already sorted subarray whenever we are shifting right a[i] (as a[j] is smaller than probed element a[i]) we are deleting the inversion pair (a[i],a[j]). so If there are at most n inversion pair insertion sort needs atmost n steps to correct all the inversion pair hence the time complexity is O(n).

1

##### Baljeet kaur Posted on Sep 14, 2019 08:50 AM

Inversions here means we gotta swap the position of elements Ai and Aj if Ai>Aj and i

0

##### Apoorv Panse Posted on Sep 17, 2019 09:03 PM

Go to this link, it is well explained there : https://gateoverflow.in/43576/gate2003-62