Question

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 a n inversions?

• A. $\Theta (n^{1.5}$)
• B. $\Theta \left(n^2\right)$
• C. $\Theta \left(nlogn\right)$
• D. $\Theta \left(n\right)$

Answer 1

The correct option is D $\Theta \left(n\right)$

Insertion sort runs in O(n + f(n)) time where f(n) denotes number of inversions.
Therefore time complexity is $\Theta \left(n\right)$.