Asymptotics claims (little o and exponentiation)

Question

I have been stuck on this for hours and would really appreciate some help with it. I have to check if those statements imply the given outcome.

a) $f(n)=o(g(n))$ implies that $3^{f(n)}=o(3^{g(n)})$

b) $3^{f(n)}=o(3^{g(n)})$ implies that $f(n) = o(g(n))$

I am really having problem with this and would appreciate your help. here's what I did:

a) seems to be a true claim.since if $f(n)=o(g(n))$ then $0\leq f(n)<cg(n)$. so in this case $3^{f(n)} <c\cdot 3^{g(n)}$, which makes it a true claim.

b) here i really don't know. if $3^{f(n)}=o(3^{g(n)})$ then it should mean $3^{f(n)}< 3^{Cg(n)}=(3^C)^{g(n)}$. I don't know how to deduct from here whether it is a true claim or not.

Thank you very much for your help.

Answer 1

So, the main takeaway here is be careful with exponentiation and asymptotics. It is not quite always what you'd expect.

---

a). This is false... first, a counterexample: $f(n) = \frac{1}{n}$, $g(n)=1$. We clearly have $f(n) = o(g(n))$ when $n\to\infty$. Yet, $$ \frac{3^{f(n)}}{3^{g(n)}} = 3^{\frac{1}{n}-1} \xrightarrow[n\to\infty]{} \frac{1}{3} > 0 $$ so we actually have $3^{f(n)} = \Theta(3^{g(n)})$. Why? $f(n)=o(g(n))$ does not mean much for $f(n)-g(n)$ (it could go to $-\infty$, or as above... to $0$. But that's the exponent of the ratio $\frac{3^{f(n)}}{3^{g(n)}}$.

b). This is false again. $3^{f(n)} = o(3^{g(n)})$ (when $n\to\infty$) is equivalent to $3^{f(n)-g(n)} = \frac{3^{f(n)}}{3^{g(n)}} = o(1)$, that is $$ \lim_{n\to\infty} 3^{f(n)-g(n)} = 0\,. $$ By continuity of the logarithm, taking $\log$'s we get $$ \lim_{n\to\infty} (f(n)-g(n)) = -\infty\,. $$ This does not imply $f(n) = o(g(n))$ either, only that the difference goes to $\infty$ (instead of the ratio going to $1$). For a counterexample: $$ f(n) = n^2, \qquad g(n) = n^2+n\,. $$

Answer 2

Recall that by definition

• $f(n) = o(g(n))\iff f(n)=\omega(n)\cdot g(n)$ with $\omega(n)\to 0$

then

• $3^{f(n)}=3^{\omega(n)\cdot g(n)}$

thus claim a) seems to be not true. Can you find a couterexample?

Try with $f(n)=\frac 1 {n^2}$ and $g(n)= \frac1n$.

For b) we have

• $3^{f(n)} = o(3^{g(n)})\iff 3^{f(n)}=\omega(n)\cdot 3^{g(n)}$ with $\omega(n)\to 0$

then

• $\log_3 3^{f(n)}=\log_3 (\omega(n)\cdot 3^{g(n)}) \implies f(n)=\log_3 (\omega(n))+g(n)$

thus also claim b) seems to be not true. Can you find a couterexample?

Try with $f(n)=\log_3 \frac 1 {n^2}$ and $g(n)= \log_3 \frac1n$.