PA of Algorithms Q113

0. What would be the worst case time complexity of the insertion sort algorithm, if the inputs are restricted to permutations of l...n with at most n inversions?

Answer
Comment
Array

Option : D
Explanation :
If array of size n with n inversion then complexity of insertion sort is Q (n)
Let us take an example.
(6 1 2 3 5 6 4)
total no. of comparision require to sort above array is 2 (n–1) = 2* 5 = 10
so complexity is Q (n).

Forgot your password?

I agree with the Terms.