Question

How many comparisons will be made in the worst case when an array of size n will be sorted by using a binary insertion sort algorithm?

(a) n

(b) 1

(c) log n

(d) n log n

This question was addressed to me in an interview for job.

My question is based upon Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (c) log n

The best explanation: Binary insertion sort makes log n comparisons in the worst case. Whereas the standard version makes n comparisons in the worst case.