The usual Θ(n2) implementation of Insertion Sort to sort an array uses linear…
2003
The usual Θ(n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
- A.
remain Θ(n2)
- B.
become Θ(n (log n)2)
- C.
become Θ(n log n)
- D.
become Θ(n)
Attempted by 429 students.
Show answer & explanation
Correct answer: A
Final complexity: Θ(n^2)
Explanation:
Finding the insertion position using binary search takes Θ(log i) time for the i-th insertion (comparisons only).
But inserting into an array requires shifting elements to make room, which can take Θ(i) time in the worst case for the i-th insertion.
Thus the total work is the sum over i = 1 to n of (log i + i).
Compute the sum: total time = ∑_{i=1}^{n} (log i + i) = Θ(n log n + n^2) = Θ(n^2).
Conclusion: Binary search reduces the number of comparisons but does not eliminate the linear cost of shifting elements in an array; therefore, insertion sort with binary search still runs in Θ(n^2) time in the worst case.