Lower bound proof without limits

Question

Prove $n^n \in \omega(n^{100})$ using the original definition

$f(n) ∈ ω(g(n))$ if $∀ c > 0, ∃ n_0 > 0$ such that $c |g(n)| < |f(n)| ∀ n ≥ n_0$

Applying this definition, we get $cn^{100} \le n^n$, and we have to show for all $c > 0$ and some $n_0 > 0$ this works.

I am confused how to proceed exactly from this inequality. Any hints?

Answer 1

Note that $$ cn^{100} \le n^n \iff c \le n^{n - 100}.$$ Given any $c>0$, take $n_0$ sufficiently large (say, $n_0 = \max\{c,101\}$), so that $n_0^{n_0 - 100}$ is greater than $c$.

• Exponent $n_0-100 \ge 101 - 100 = 1$
• base $n_0 \ge c \ge 1$: $n_0^{n_0 - 100} \ge n_0 \ge c$
• or base $n_0 \ge 1 > c$: $n_0^{n_0 - 100} \ge1 > c$

Since $n \mapsto n^{n - 100}$ is increasing (increasing base and exponents) starting from $n_0$, for all $n \ge n_0$, we have $n^{n-100}\ge c$. This shows that $n^n \in \omega(n^{100})$.