patternCritical
Why is the log in the big-O of binary search not base 2?
Viewed 0 times
whythesearchlogbigbinarynotbase
Problem
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)$?
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)$?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#78083, answer score: 87
Revisions (0)
No revisions yet.