Question

C++

6. Insertion sort is n^2 because every item has to be compared against every item. What if instead of looping through the left hand you used a binary search on the left hand to find the insertion place. What would the new Big O be and why?

Answer 1

Insertion Sort:

The insertion sort algorithm starts from the second element and puts this element at its exact location by swapping or interchange with the first element and so on until the end of the array.

• Best case running time = O(n)
• Worst-case running time = O(n² )
• Average case running time = O(n²)

In an already sorted array of size n, the total number of comparisons is n-1.

If we use binary search to find the location of the inserted element then also the run time complexity will remain the same as O(n²) but the number of comparisons will decrease.

The binary search will take O(log n) compare.

So, the total number of compare for sorting will be O(n log n).