# Big O notation doubt f(n) = g(n)

If $$f(n) = g(n) = n$$

then Is $$f(n) = O(g(n))$$

As far as I know it is according to the definition of Big-O notation. So, if this is the precondition then Is

$$2^{f(n)} = O(2^{g(n)})$$

?

I am confused if this equality holds ?

-
When exponentiating, the constant factor implicit in the Big-O notation can play a big role on the asymptotics of the result, as Brian's answer shows. –  Antonio Vargas Mar 3 '13 at 18:46

Consider $f(n)=2n$ and $g(n)=n$; then $f(n)$ is $O\big(g(n)\big)$, but
$$\lim_{n\to\infty}\frac{2^{f(n)}}{2^{g(n)}}=\lim_{n\to\infty}\frac{2^{2n}}{2^n}=\lim_{n\to\infty}2^n=\infty\;,$$
so $2^{f(n)}$ is not $O\left(2^{g(n)}\right)$.
Can you be a bit elaborate. Sorry if it is quite basic. Why are we taking a lim of f(n) and g(n). From that statement how are we inferring the final statement ? –  Chaitanya Mar 4 '13 at 5:49
@Chaitanya if $a(n)/b(n)$ is unbounded then it is not true that $a(n) = O(b(n))$. Think about the definition of Big O notation: if $a(n) = O(b(n))$ then we can find a constant $C$ such that $|a(n)/b(n)| \leq C$, right? –  Antonio Vargas Mar 6 '13 at 4:02
@AntonioVargas Correct. Thanks a lot. :) Basically, the constant C should not be dependent of n and should be finite even if n goes to infinity. –  Chaitanya Mar 6 '13 at 6:36
@Chaitanya: That’s right. (Sorry about missing your first question.) When $f$ is $O(g)$, so that you have $f(n)\le cg(n)$ for all $n\ge n_0$, then \frac{f(n)}{g(n)}\le c$for all$n\ge n_0\$. –  Brian M. Scott Mar 6 '13 at 13:25