# Asymptotic relationship of logarithms in different bases

I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true).

For the functions $\lg n$ and $\log_8 n$, what is the asymptotic relationship between these functions. Select all that apply.

[  ] $\lg n$ is $O(\log_8 n)$
[  ] $\lg n$ is $\Omega(\log_8 n)$
[  ] $\lg n$ is $\Theta(\log_8 n)$

Why is this the case? I thought that the answer would be only the first one: $\log_2 n$ would be the upper bound of $\log_8 n$. Can someone explain this to a noob?

We'll show two results. The first is that for any positive constant $k$, we'll have $$k\cdot f(n) = O(f(n))$$ To see this, recall what it means for $g(n)=O(f(n))$: this is true when we can find two constants $c>0, N\ge 0$ such that $g(n)\le c\cdot f(n)$ for all $n\ge N$. If we choose $g(n)$ to be $k\cdot f(n)$ then we have just what we need: we'll just use $k$ for our constant $c$ and select any $N$ we want. It's trivial to adapt this argument to big-$\Omega$, and so it also holds for big-$\Theta$ as well.
The second result we need is that logs to different bases are always going to be constant multiples of each other, namely $$\log_ax=(\log_ab)\log_bx$$ This is easy to see: just raise $a$ to each side power and you'll wind up with equal results.
In the problem stated, assuming that $\lg n$ is $\log_2n$, we'll have $$\lg n=(\log_2 8)\log_8n=3\log_8n$$ and the two logs will differ only by a multiple of 3, which as we showed above, means that $\lg n$ and $\log_8n$ are the same function, as far as big-whatever notation is concerned.