How to prove $2^n = \omega (n^k)$

Question

I'm trying to prove $2^n = \omega (n^k)$ but the problem is that, I could not find any examples of proving little/ small omega, and what makes it confusing is that I could not even find a way to deal with $k$.

I tried this: $$2^n > c (n^k).$$

If I take the logarithm of both sides, I get $$n > c (\log(n))^k = n > ck\log(n),$$ but then I'm lost!

I could solve it if it were Big-$O$ but for both big-$\Omega$ and small-$\omega$ I feel as I know nothing about math :(

I do not expect the answer as much as I expect a hand to lead me at least understand what going when it comes to Omega.

Thank you, but what the next stop after that? I'm totally lost and could not make ant forward step after choosing c = K^2 + 1 — Naif Alghamdi, Sep 09 '13 at 17:29

score 0 · Accepted Answer · answered Sep 09 '13 at 05:52

0

$$\begin{align} 2^n >& cn^k\\ n \log 2 >& \log c + k \log n\\ n \log 2 - k\log n >& \log c \end{align}$$

Now, since the left hand side function of $n$ has a derivative of $\frac{n\log 2-k}{n}$, for $n>\frac{k}{\log2}$ the function is increasing. And since the function will grow unbounded (limit at infinity is infinity), this function will be greater than any constant $\log c$ either for large $n$.

answered Sep 09 '13 at 05:52

peterwhy

22,256

Thank you very much, very clear – Naif Alghamdi Sep 09 '13 at 17:28
Can we say for n > k ? as log2 = 1 ! – Naif Alghamdi Sep 09 '13 at 18:37

How to prove $2^n = \omega (n^k)$

1 Answers1

Linked

Related