Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Related / duplicate: Why is the log in the big-O of binary search not base 2? $\endgroup$– Bernhard BarkerCommented May 22, 2019 at 9:16
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.
If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.
-
6$\begingroup$ I guess this is only going to come up with something like $2^{\sqrt{\log n}}$. I can't see any reason for expressing a number as $2^{c\log_b n}$ rather than $n$-to-the-whatever-it-is (except perhaps as an intermediate stage of a calculation). $\endgroup$ Commented May 21, 2019 at 19:45
-
11$\begingroup$ +1 for "constant factors matter in exponents" $\endgroup$ Commented May 21, 2019 at 22:57
$\begingroup$
$\endgroup$
5
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log_a n = \Theta(\log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered May 20, 2019 at 17:34
-
16$\begingroup$ I prefer to see $\in$ instead of $=$ $\endgroup$– NayukiCommented May 21, 2019 at 22:04
-
17$\begingroup$ I'm afraid the standard notation uses $=$. $\endgroup$ Commented May 21, 2019 at 22:05
-
7$\begingroup$ @YuvalFilmus The standard notation is misleading, completely different to the standard everywhere else and makes algorithmic complexity seem completely alien from things quite similar to it. "It's the standard notation" should never be a reason to favour a bad solution over a better, similarly-clear one. (The meaning of the symbol is usually clear from context, anyway.) $\endgroup$ Commented May 22, 2019 at 18:16
-
8$\begingroup$ @wizzwizz4 Common practice is an excellent reason. It promotes efficient communication. That’s the reason we all put up with the quirks of English spelling. $\endgroup$ Commented May 22, 2019 at 20:04
-
4$\begingroup$ Sometimes $n \mapsto \log_a n \in \Theta ( n \mapsto \log_b n)$ just has too much stuff there to be clearer than $\log_a n = \Theta (\log_b n)$. $\endgroup$– JiKCommented May 23, 2019 at 10:48
$\begingroup$
$\endgroup$
As $\log_xy = \frac{1}{\log_y{x}}$ and $\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$, so $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. As $\log_a{b}$ is positive constant (for all $a,b > 1$), so $\log_a{n} = \Theta(\log_b{n})$.
$\begingroup$
$\endgroup$
In most cases, it's safe to drop the base of the logarithm because, as other answers have pointed out, the change-of-basis formula for logarithms means that all logarithms are constant multiples of one another.
There are some cases where this isn't safe to do. For example, @gnasher729 has pointed out that if you have a logarithm in an exponent, then the logarithmic base is indeed significant.
I wanted to point out another case where the base of the logarithm is significant, and that's cases where the base of the logarithm depends directly on a parameter specified as input to the problem. For example, the radix sort algorithm works by writing out numbers in some base $b$, decomposing the input numbers into their base-$b$ digits, then using counting sort to sort those numbers one digit at a time. The work done per round is then $\Theta(n + b)$ and there are roughly $\log_b U$ rounds (where $U$ is the maximum input integer), so the total runtime is $O((n + b) \log_b U)$. For any fixed integer $b$ this simplifies to $O(n \log U)$. However, what happens if $b$ isn't a constant? A clever technique is to pick $b = n$, in which case the runtime simplifies to $O(n + \log_n U)$. Since $\log_n U$ = $\frac{\log U}{\log n}$, the overall expression simplifies to $O(\frac{n \log U}{\log n})$. Notice that, in this case, the base of the logarithm is indeed significant because it isn't a constant with respect to the input size. There are other algorithms that have similar runtimes (an old analysis of disjoint-set forests ended up with a term of $\log_{m/2 + 2}$ somewhere, for example), in which case dropping the log base would interfere with the runtime analysis.
Another case in which the log base matters is one in which there's some externally-tunable parameter to the algorithm that control the logarithmic base. A great example of this is the B-tree, which requires some external parameter $b$. The height of a B-tree of order $b$ is $\Theta(\log_b n)$, where the base of the logarithm is significant in that $b$ is not a constant.
To summarize, in the case where you have a logarithm with a constant base, you can usually (subject to exceptions like what @gnasher729 has pointed out) drop the base of the logarithm. But when the base of the logarithm depends on some parameter to the algorithm, it's usually not safe to do so.
answered May 22, 2019 at 17:37
$\begingroup$
$\endgroup$
Let $f_k(n)=\log_kn$,$k>2$, and let $t(n)=\log_2n$.
You can rewrite $f_k(n)$ as follow $$f_k(n)=\frac{\log_2n}{\log_2k}$$ Now $k$ have two states:
- $k$ is constant:
$$\lim_{n\to \infty}\frac{f_k(n)}{t(n)}=\lim_{n\to \infty}\frac{\frac{\log_2n}{\log_2k}}{\log_2n}=c$$ that $c$ is a constant$>0$, hence $$t(n)=\Theta(f_k(n)).$$ So there is no difference between $f_k(n)$ , and $t(n)$ in terms of asymptotic notation.
- $k$ isn't constant:
$$\lim_{n\to \infty}\frac{f_k(n)}{t(n)}=\lim_{n\to \infty}\frac{\frac{\log_2n}{\log_2k}}{\log_2n}=0$$
So $t(n)$ have faster growth rate and $$t(n)=\omega(f_k(n)).$$
