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)
Answers
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
© 2024 - All rights are reserved- AAIC Technologies pvt ltd