In a permutation a1.....an of n distinct integers, an inversion is a pair (ai,…
PYQ GATE 2003
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)
Attempted by 643 students.
Sign up free to check your answer
Sign up freeLoading lesson…