Gate2003_62

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) \(\Theta\)(n2)
(B) \(\Theta\)(n log n)
(C) \(\Theta\)(n1.5)
(D) \(\Theta\)(n)

Discuss

1Comment
ALOK GUPTA @galok1001 8 Jul 2018 11:13 am
d