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.


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
            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?

  • 1
    $\begingroup$ While waiting for this question to be marked duplicate, have a look at system behind algorithm analysis. $\endgroup$
    – greybeard
    Nov 23, 2019 at 14:07
  • 1
    $\begingroup$ Big O notation allows multiplicative constants. $\endgroup$ Nov 24, 2019 at 15:44

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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