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)
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)$.
