Multiple choice

The usual O(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

  1. remain O (n2)

  2. become O (n (log n)2)

  3. become O (n log n)

  4. become O (n)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Binary search is efficient when the sorted sequence is there, but the worst case scenario for insertion sort would not be sorted sequence so even using binary search instead of linear search the complexity of comparisons will remain O (n2)

Keep practicing — related questions