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

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

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

0

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

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