1
$\begingroup$

Why is binary search time complexity for worst case log (n) + 1 instead of just being log(n)? the way I understand it, the number of times we divide the list till we find our desired element is log (n) times in the worst case scenario. Where does this extra 1 come from? (it's log (n) + 1 according to the power point of my class)

$\endgroup$
1
$\begingroup$

The exact number depends on your assumptions, so either is defensible. If you assume that the number you're searching for is definitely in the list, and it's just a matter of finding it, then the number of comparisons needed can be as large as $\lceil \lg n \rceil$, and won't be any larger than that. (Here $\lceil \cdot \rceil$ represents rounding up to the nearest integer.) Since $\lceil \lg n \rceil \le 1 + \lg n$, it is not unreasonable to describe the worst-case number of comparisons needed as $1 + \lg n$. Again, as a reminder, this assumes that the number you're searching for is definitely present.

That said, in theoretical analysis, we usually ignore constant factors. So, we summarize the running time as $O(\lg n)$. For these purposes, there is no difference between $\lg n$ or $\lg n+1$; they are both $O(\lg n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.