# Worst case runtime for binary search

The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element. It takes 4 comparisons in the example below.

python2.7

def binary_search(a_list, item, comparisons_inner=0):
low = 0
high = len(a_list) - 1

while low <= high:
mid = (low + high) / 2
guess = a_list[mid]
comparisons_inner += 1
if guess == item:
return mid, comparisons_inner
if guess > item:
high = mid - 1
else:
low = mid + 1
return None, comparisons_inner

my_list = [5, 8, 11, 15, 21, 23, 100, 223]
index, comparisons = binary_search(my_list, 223)
print(index, comparisons)


log(8) < 4
Why is the run time of binary search O(log(n)) despite the 4 comparisons it takes in the example above?

• While waiting for this question to be marked duplicate, have a look at system behind algorithm analysis. – greybeard Nov 23 '19 at 14:07
• Big O notation allows multiplicative constants. – Yuval Filmus Nov 24 '19 at 15:44

Your algorithm makes $$\lfloor \log n \rfloor+ 1$$ comparisons for an array of length $$n$$, which is at most $$2 \log n$$, which is $$O(\log n)$$. Hence, $$\lfloor \log n \rfloor+ 1 = O(\log n)$$.
In more detail, recall that the big-O notation subsumes constant factors. A function $$f(n)$$ is said to be $$O(\log n)$$ if there exist positive constants $$c$$ and $$n_0$$ such that $$f(n) \le c \log n$$ for all $$n \ge n_0$$. In our case, we want to prove $$\lfloor \log n \rfloor +1 = O(\log n)$$. To prove the existence of positive constants $$c$$ and $$n_0$$ satisfying the desired condition, observe that $$\lfloor \log n \rfloor+ 1 \le \log n + \log n = 2 \log n$$, for all $$n \ge 2$$. So we can take $$c = 2$$ and $$n_0 = 2$$.