GATE CS Applied Course



In a permutation 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)



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).


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


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

Go to this link, it is well explained there :

© 2024 - All rights are reserved- AAIC Technologies pvt ltd