Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Often, when I encounter big-O notation during computations, the basis of the logarithm is omitted. Is there an error, or is it in some sense irrelevant? Or am I missing something?
For instance, $\log_2 n$ is often indicated as $O(\log n)$. However, sometimes I also see it as $O(\log_2 n)$ so this is confusing me.
This is due to the property of logarithm's basis.
From the basis change formula of logarithms, you get: $$\log_a n = \frac{\log_b n}{\log_b a} \, $$
and $\log_b a$ is a constant with respect to your variable $n$. Thus, $O(\log_a n)=O(\frac{\log_b n}{\log_b a}) = O(\log_b n)$.
This means that you can either write $O(\log_2 n)$ or omit it and write $O(\log n)$ (which usually refers to the natural basis $e$, also written as $\ln n$), because it makes no difference.
The difference between $\log_2$ and any of the other commonly used logs (base 10 or base $e$) is just multiplication by some order $1$ constant so that might be why it isn't so relevant.
$$\log_{10}x = \frac{\log_n x}{\log_n10}$$ and for $n=e,2$ the factor on the bottom is negligible ish.
This answer isn't going to be fun, but I'm going to be pedantic here to justify why it's okay to ignore constants in big-$O$ by using the formal definition.
Definition: Let $f$ and $g$ be functions that map from $\mathbb{N}$ to $\mathbb{N}$. We say that $f \in O(g)$ ("$f$ is in big-$O$ of $g$") iff: $\exists k \in \mathbb{N}, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[n > n_0 \Rightarrow f(n) < k \cdot g(n)\right]$.
In English, that says there exists a constant $k$ and a constant $n_0$ such that every $n$ greater than $n_0$ will imply that $f(n) < k \cdot g(n)$. The constant $k$ controls how much to scale the function $g$, and the constant $n_0$ controls how many small numbers to ignore.
We know from the change-of-base formula that $\displaystyle\log_b a = \frac{\ln a}{\ln b}$.
Claim: For any $a, b > 1$, we have that $f \in O(\log_a n)$ if and only if $f \in O(\log_b n)$.
Given on the left side that $f \in O(\log_a n)$, we know that there must exist constants $k$ and $n_0$ to satisfy the big-$O$ definition. To make it satisfy the definition for $f \in O(\log_b n)$ on the right side, we take $k' = k \frac{\ln b}{\ln a}$ and the same $n_0$, and the formula will work out.
In conclusion, it is redundant for big-$O$ purposes to write the base of the logarithm as long as it greater than one. So writing a vague-looking $f \in O(\log n)$ loses no information.
