up vote 4 down vote favorite
2

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 $s = log_2(n)$. So wouldn't the average number of steps for the binary search algorithm be $log_2(n)$?

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

share|cite
up vote 12 down vote accepted

When you change the base of logarithm the resulting expression differs only by a constant factor which is usually ignored when you apply big-$O$ notation. 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$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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