##### 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 8 Jul 2018 11:13 am
d