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?
(B) \(\Theta\)(n log n)