Prove that $f(n)=n^{100} \in \Omega(2^{n/100}) $

524 Views Asked by At

I know that $f(n)$ grows asymptotically faster than $g(n)$

By definition I know that
$f(n)=\Omega (g(n))$ given $c$ and $n_0$ such that $f(n) \geq c *g(n), \forall n \geq 1 $

Then I need to show that such $c$ and $n_0$ exist

$$ \Rightarrow n^{100} \geq 2^\frac{n}{100}, \forall n \geq 1\\ 2^\frac{n}{100} = \sqrt[100]{2^n} \\ \Rightarrow n^{100} \geq \sqrt[100]{2^n}\\ \Rightarrow 2n^{100} \geq 2\sqrt[100]{2^n}\\ \therefore f(n)=n^{100} \geq 2\sqrt[100]{2^n}, \forall n\geq1 $$ But this last step isn't true, how to find the $c$ that multiplies $g(n)$ if every constant makes false the last assumption?

1

There are 1 best solutions below

1
On BEST ANSWER

You're correct that there's an issue; in fact, $$n^{100}=o\left(2^{n/100}\right).$$ If $n^{100}$ were $\Omega\left(2^{n/100}\right)$, then there would be some constant $c$ for which $$n^{100}\geq c2^{n/100}$$ for large $n$, which implies $$n^{10000}\geq C2^n$$ for some constant $C=c^{100}$. Taking $n=2^m$ for large $m$, we need $$2^{10000m}\geq C2^{2^m}.$$ Can you finish the proof from here to show a contradiction?