2
$\begingroup$

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?

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

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

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