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