$\forall k \in \mathbb{N},n^n \notin O(n^k)$

Question

$\forall k \in \mathbb{N},n^n \notin O(n^k)$

Show $\forall k \in \mathbb{N},\forall c,n_0 \in \mathbb{R^+},\exists n \in \mathbb{N}, n \geq n_0 \wedge n^n\ > cn^k$

Proof.

let $k \in \mathbb{N}, c,n_0 \in \mathbb{R^+},n= {\lceil}max\{c,k,n_0\}{\rceil}+1$

Case1:$n= {\lceil}c{\rceil}+1$

Show $( {\lceil}c{\rceil}+1)^{ {\lceil}c{\rceil}+1}>c( {\lceil}c{\rceil}+1)^k$

Since $c>k$

That $ {\lceil}c{\rceil}>k$

Have $ {\lceil}c{\rceil}-k>0$

Add one to both side have $ {\lceil}c{\rceil}-k+1>1$

Therefore $( {\lceil}c{\rceil}+1)^{ {\lceil}c{\rceil}+1-k}> {\lceil}c{\rceil}+1>c$

That $( {\lceil}c{\rceil}+1)^{ {\lceil}c{\rceil}+1-k}( {\lceil}c{\rceil}+1)^k>c( {\lceil}c{\rceil}+1)^k$

Have $n^n>cn^k$ hold

Case2:$n= {\lceil}k{\rceil}+1$

Show $( {\lceil}k{\rceil}+1)^{ {\lceil}k{\rceil}+1}>c( {\lceil}k{\rceil}+1)^k$

Same as $( {\lceil}k{\rceil}+1)( {\lceil}k{\rceil}+1)^{k}>c( {\lceil}k{\rceil}+1)^k$

Since $k>c \wedge {\lceil}k{\rceil}+1>k$

That $ {\lceil}k{\rceil}+1>c$

Have $n^n>cn^k$ hold

Case3:$n= {\lceil}n_0{\rceil}+1$

Show $( {\lceil}n_0{\rceil}+1)^{ {\lceil}n_0{\rceil}+1}>c( {\lceil}n_0{\rceil}+1)^k$

Since $n_0>k \wedge {\lceil}n_0{\rceil} \geq n_0$ That $ {\lceil}n_0{\rceil} > k$

Have $ {\lceil}n_0{\rceil}-k>0$

Add one to both side have $ {\lceil}n_0{\rceil}-k+1>1$

Therefore $( {\lceil}n_0{\rceil}+1)^{ {\lceil}n_0{\rceil}+1-k}> {\lceil}n_0{\rceil}+1>c$

That $( {\lceil}n_0{\rceil}+1)^{ {\lceil}n_0{\rceil}+1-k}( {\lceil}n_0{\rceil}+1)^k>c( {\lceil}n_0{\rceil}+1)^k$

Have $n^n>cn^k$ hold

Q.E.D

Answer 1

I guess you want a proof using the algebraic definition, in which case, for all $k\in\Bbb N$ and $c,n_0\in\Bbb R^+$, choose $n\in\Bbb N$ such that $n\gt\max\{k,n_0,c\}$, then for some $m\geq 1$, we have $$n^n=n^m\cdot n^k\gt cn^k$$

since $n^m\gt c$ as $n^m\geq n^1\gt c$.

---

The proof in the other answer is equivalent by the limit definition of Big-O notation.

Answer 2

As for all constant $k \in \mathbb{N}$, $\lim_{n\to\infty}\frac{n^k}{n^n} = 0$, $n^n \not\in O(n^k)$ for all constant $k \in \mathbb{N}$.