small medium large xlarge

Hi,

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.

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.