I understand that binary search time grows proportionally to log_2(N).
The bin_sort function on Page 260 of the book does a binary search of result (to find out where to put the next item in values) and then inserts that item into result with the appropriate index.
On that same page towards the bottom, it says that “..actually inserting it takes time as well. To create an empty slot in the [result] list, we have to move all the values above that slot up one place. On average, this means copying half of the list’s values, so the cost of insertion is proportional to N.”
I can wrap my head around this for the most part. But the solution to Problem 8 at the end of the chapter reads:
“On the first iteration, binary search is performed on only 2 items; on each iteration, the size of the sublist being searched grows by one. So N log_2 N is an upper bound on the estimate of the overall running time, but not an egregious one.”
1) On the first iteration, isn’t binary search performed on a list of length 0? The result list is empty!
2) I assume the exercise question is only addressing the issue of the search time and not the insertion time (as addressed at the bottom of page 260). Is this correct?
3) Is N*log_2(N) equivalent to the total searching time if on every iteration, the binary search took the maximum amount of attempts to find the correct index? If so, can someone please provide some examples of when this actually happens with any large lists?
I had some other questions but I kind of figured them out as I was writing this.
P.S. Thanks for this great book and resourceful website