How do I determine if there exists a function $f$, such that
\begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation}
Is true or false?
I tried using the c and No method but cannot come up with a solution
Here is a counterexample:
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$.