0
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

In simple terms: Asymptotic notation ignores constant multiples.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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