# Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that

$$f(n) = {\mathcal O}(\log n),$$ but $$2^{f(n)} ≠ {\mathcal O}(n).$$

Is true or false?

I tried using the c and No method but cannot come up with a solution

-
What do you mean by "$2f(n)\neq O(n)$ is true or false"? And do you mean $2^{f(n)}$ (since we were dealing with logs earlier)? –  tabstop Feb 5 at 15:34
@tabstop yes I just changed it –  user126032 Feb 5 at 15:36
Wouldn't that always be true unless the logarithm were base $2$? –  recursive recursion Feb 5 at 15:36
@recursiverecursion note that $\log_a \in \mathcal O (\log_b)\ \forall\ a,b>0$ –  AlexR Feb 8 at 15:32

Take $f(n)=k\log n=\log n^k$, where $k=\dfrac{2}{\log 2}$. Then clearly, $f(n)={\mathcal O}(\log n)$.
At the same time $$2^{f(n)}=2^{\log n^k}=\mathrm{e}^{(k\log 2)\log n}=\mathrm{e}^{2\log n} =\mathrm{e}^{\log n^2}=n^2,$$ but the function $2^{f(n)}=n^2$ is definitely not ${\mathcal O}(n)$, as $$\frac{2^{f(n)}}{n}\to \infty,$$ when $n\to\infty$.