Prove $n^2 \not \in \Omega(2^n)$

Question

I can use the fact that $\log(n) \in O(n)$ and $n \notin O(\log(n))$.

So assume for the sake of contradiction that $n^2 \in \Omega(2^n)$.

Hence, there exists some $c > 0$ and $k > 0$ such that for all $n > k$ we have $c \cdot 2^n \leq n^2$.

Hence, we have that $\log(c) + 2\log(n) \leq n\log(2)$. Hence, $\log(c) \leq n\log(2) - 2\log(n)$.

I know that $n\log(2) - 2\log(n)$ approaches negative infinity. But I'm having trouble showing this formally using $\log(n) \in O(n)$ but $n \notin O(\log(n))$. And I can't use any other facts from calculus.

Answer 1

Hint: You know that $$\lim_{n \to \infty} \frac{\log_2 n}{n} = 0.$$ This means that means that for any positive constant $k$, $k \log_2 n - n$ gets arbitrarily large and negative as $n$ increases (why?). What does this imply about the quantity $2^{2 \log_2 n - n}$?

Answer 2

I bring one way without using limits. Firstly Let's start with $$n< 2^n, \forall n \in\mathbb{N}$$ I'll use formula $ a^{n}-b^{n}=(a-b)(a^{n-1} + ba^{n-2}+ ... + b^{n-1}) $, which is easy to proof simply open brackets on right hand side: $$2^{n} = 2^{n} - 1 + 1 = 1+2+ ... +2^{n-1} +1 > n $$ Taking logarithm with base $2$ gives $$\log_2 n< n, \forall n \in\mathbb{N}$$ So we have $\log_2 (n) \in O(n)$.

To show, that $n\notin O(\log_2 (n))$ we can use inequality $\frac{n}{b^n}<1$, which holds for any $b>1$ in some neighborhood of infinity.