small medium large xlarge

22 Aug 2015, 18:33
Abaas K (1 post)

Hello everyone,

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

24 Sep 2015, 14:11
Jennifer Campbell (17 posts)

1) Yes, you are correct that the first time bisect.insort_left(result, v) is called, the list result is empty.

2) Yes, your assumption is correct.

3). Yes, we are giving the upper-bound. In other words, we can rely on the algorithm performing no worse than that. As mentioned on page 266, the upper-bound allows us to classify algorithms based on their performance in the worst case.

  • Jen Campbell
You must be logged in to comment