Question

The worst case time complexity of insertion sort is O(n^2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?

(a) O(nlogn)

(b) O(n^2)

(c) O(n)

(d) O(logn)

The question was asked by my school principal while I was bunking the class.

Question is taken from Insertion sort topic in portion Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (b) O(n^2)

For explanation: The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n^2) because of the series of swapping operations required for each insertion.