Question 9639 – Sorting
April 18, 2024GATE 1992
April 18, 2024Sorting
|
Question 9
|
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?
|
Θ(n2)
|
|
|
Θ(n log n)
|
|
|
Θ(n1.5)
|
|
|
Θ(n)
|
Question 9 Explanation:
Here the inputs are to be restricted to 1…n with atmost ‘n’ inversions. Then the worst case time complexity of inversion sort reduces to Θ(n).
Correct Answer: D
Question 9 Explanation:
Here the inputs are to be restricted to 1…n with atmost ‘n’ inversions. Then the worst case time complexity of inversion sort reduces to Θ(n).