i did not understand the question properly.
Question is unclear
Please paste the question here.
Q4. Insertion Sort
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?
O(n^2)
O(nlogn)
O(n^1.5)
O(n)