Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 6 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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