small medium large xlarge

23 Jun 2017, 18:29
Nick Perrin (1 post)


Firstly just wanted to point out that the exercise #3 in Chapter 13 asks to compare Binary search to the “built-in search”, yet the solution compares Binary search and linear search. Seems to be a discrepancy there.

My question is about the solution, however. At the following step: “ [N is much larger than log_2 N, so we simplify the denominator and multiply the numerator by 2 (remember, we want a rough answer)] “ I don’t understand this logic. I know a rough answer is fine, but how do we just get rid of the ‘ - 2log_2N’? Is it just because subtracting it would have a negligible effect on the value of N, so our ‘rough answer’ can handle that inaccuracy?

But especially, why do we multiply the numerator by 2? I can’t seem to figure out this reasoning, rough or not.

Thanks for your help!

17 Jul 2017, 17:38
Paul Gries (46 posts)

For your first question, the reason why linear search comes up is because that’s what built-in function index uses. It certainly is confusing not to mention this in the question, although this is discussed in section 13.1 Searching a List.

For your real question, it looks like you found a mistake! We think it makes sense until here:

(N log_2 N) / (N - log_2 N) < k

But the rest of the calculations don’t make sense.

You must be logged in to comment