Disprove Big-O statement

Question

Prove of disprove $\exists k \in \mathbb{N}, n^n \in \mathcal{O}(n^k)$. I realized that I need to disprove, rewrote the statement with negation and Big-Oh definition expanded, and now struggling on how to algebraically prove $n^n>cn^k$ for all $c, k$ while only picking a value for $n$ and knowing that $n > n_0$. Any help appreciated, been stuck on it for days. Thank you!

Answer 1

Let $n_0>k$, then $n^n = n^kn^{n-k}>cn^k$. Note that for any $c$ you can find $n$ large enough so that $n^{n-k}>c$. Just take $n=\max(c, k)+1$ for example.