Please explain me the question, unable to understand it properly, whether it is asking for the time complexity of insertion sort or it is trying to convey some other thing, because what I am able to get is it is giving i < j specifying index and ai > aj, that we have to sort in decreasing order using insertion sort.
Quiz on Sorting q4
Please mention the question too, so that i can respond accordingly.
I thought might T.A’s have access to questions of the course,i.e, I just specify question number?
Q:-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)
It’s but the order is jumbled
As far as of this question refer to this link, it’s well explained
Quiz answer 4