34
$\begingroup$

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.

In a size of $s = 2^n$ elements, it would take, on average, $n$ steps to find a particular element. Taking the base 2 logarithm of both sides yields $\log_2(s) = n$. So wouldn't the average number of steps for the binary search algorithm be $\log_2(s)$?

This Wikipedia article on the binary search algorithm says that the average performance is $O(\log n)$. Why is this so? Why isn't this number $\log_2(n)$?

$\endgroup$
86
$\begingroup$

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior.

For example $$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where $C = \frac{1}{\log_{2}10}$.

So $\log_{10}n$ and $\log_{2}n$ differs by a constant $C$, and hence both are true: $$\log_{10}n \text{ is } O(\log_{2}n)$$ $$\log_{2}n \text{ is } O(\log_{10}n)$$ In general $\log_{a}{n}$ is $O(\log_{b}{n})$ for positive integers $a$ and $b$ greater than 1.

Another interesting fact with logarithmic functions is that while for constant $k>1$, $n^k$ is NOT $O(n)$, but $\log{n^k}$ is $O(\log{n})$ since $\log{n^k} = k\log{n}$ which differs from $\log{n}$ by only constant factor $k$.

$\endgroup$
  • $\begingroup$ Not only for positive integers: For all real $a,b > 1$, e.g. $e$. $\endgroup$ – nbubis Jul 20 '17 at 6:25
  • 2
    $\begingroup$ I would add that this is the reason why with big-O notation, the base of the logarithm is commonly not specified. It also means there is no confusion about which base $O(\log n)$ uses: it can be any of the commonly used based, since it doesn't make a difference. $\endgroup$ – svick Jul 20 '17 at 10:57
9
$\begingroup$

In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on context. In pure mathematics, the base is almost always assumed to be $e$ (unless specified), while in certain engineering contexts it might be 10. In computer science, base 2 is so ubiquitous that $\log$ is frequently assumed to be base 2. That wikipedia article never says anything about the base.

But, as has already been shown, in this case it doesn't end up mattering.

$\endgroup$
  • 7
    $\begingroup$ It is probably further worth noting then that while "log(n)" might be ambiguous that "O(log(n))" is not because the latter only has one meaning, no matter what base you might be thinking of. $\endgroup$ – Chris Jul 20 '17 at 16:12

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.