1

Given that $f(n) = \omega(\log n)$ I need to prove that $n=O(2^{f(n)})$.
I tried the following
$f(n) = \omega(\log n) \implies \lim_{n \to \infty} \frac{\log n}{f(n)} = 0$
Then, I want to substitute $n=2^t \implies t=\log n$.
Noting that when $n \to \infty, t \to \infty$.
$\lim_{t \to \infty} \frac{t}{f(2^t)} = 0$

From now on I am not sure how to continue. Am I following the right direction? would appreciate slight guidance on how to continue.

Bernard
  • 175,478
Eliran Turgeman
  • 183
  • The statement is false. Take $f(n)=C^{-1}\log_2{n}$ with $C > 1$. Then $2^{f(n)}=n^{1/C}=o(n)$. – Aphelli Nov 04 '20 at 14:10
  • @Mindlack you mean that the statement $f(n) = \omega(logn) \implies n=O(2^{f(n)})$ is false? if so, your counter example doesn't satisfy $f(n) = \omega(logn)$ – Eliran Turgeman Nov 04 '20 at 14:21
  • Just so I understand the question, is this the same as asking you to prove that $n=O(2^{\omega log(n)})$? – roundsquare Nov 04 '20 at 14:22
  • What do you mean by the notation $\omega(\log n)$? – Greg Martin Nov 04 '20 at 15:09
  • 2
    @Eliran Turgeman: Oops. I just realized that $\omega$ and $\Omega$ weren’t actually the same thing. Sorry. In this case just note that $f(n) \geq \log_2{n}$ for $n \geq n_0$ and apply $2^{\cdot}$ to both sides of this inequality. – Aphelli Nov 04 '20 at 15:11
  • 1
    @roundsquare ... the notation $\omega$ is an asymptotic thing (like $O$ and $o$). So $f(n) = \omega(\log n)$ means $\lim_{n \to \infty} \frac{\log n}{f(n)} = 0$. – GEdgar Nov 04 '20 at 15:25
  • Oh, sorry, my bad. Deleting my comment. – roundsquare Nov 04 '20 at 15:31
  • Just so I can check my understanding. Since $f(n)=\omega (log(n))$ we can say that $lim_{n\rightarrow\infty} \frac{n}{n^{f(n)}}\geq lim_{n\rightarrow\infty} \frac{n}{n^{log(n)}} = 1$ which proves this, right? I guess that is essentially @Mindlack 's proof a bit more explicitly? – roundsquare Nov 04 '20 at 16:03
  • 1
    @roundsquare: your denominators should consist of powers of $2$, not $n$. – Aphelli Nov 04 '20 at 17:05
  • Man.... I'm really rusty. @Mindlack, other than that, is it correct? Corrected proof: Since $f(n)=\omega (log(n))$ we can say that $lim_{n\rightarrow\infty} \frac{n}{2^{f(n)}}\geq lim_{n\rightarrow\infty} \frac{n}{2^{log(n)}} = 1$. – roundsquare Nov 04 '20 at 17:33
  • 1
    @roundsquare: yes, I think that's true. – Aphelli Nov 04 '20 at 17:45

0 Answers0