In a permutation a1.....an of n distinct integers, an inversion is a pair (ai,…
2003
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?
- A.
Θ (n2)
- B.
Θ (n*log(n))
- C.
Θ (n1.5)
- D.
Θ (n)
Attempted by 318 students.
Show answer & explanation
Correct answer: D
Answer: Θ(n)
Reasoning:
Let INV be the number of inversions in the permutation.
When insertion sort inserts the i-th element, it shifts past exactly the elements before it that are greater than it. Each such shift corresponds to one inversion whose second element is that i-th element.
Summing over all elements, the total number of shifts equals INV. The algorithm also does at most a constant amount of additional work per element (for example, checks), contributing Θ(n).
Therefore the running time is Θ(n + INV).
Since the inputs are restricted to permutations with at most n inversions (INV ≤ n), the running time becomes Θ(n + n) = Θ(n). Thus the worst-case time complexity under this restriction is Θ(n).