How would you disprove the following: $ \exists k \in \mathbb{N}, n^n \in O(n^k) $.
I am aware that I have to pick a value for $n \in \mathbb{N} $ that will give us $n^n > c*n^k$ but I can't seem to figure out how to pick such a value when c and k are universally quantified.
Any tips or hints would be appreciated.
Let $k,c>0$. Then if $n>2$ and $n>k+\log_2(c)$ we get $n^n=n^{n-k}n^k>2^{\log_2(c)}n^k=cn^k$. Take, for example, $n=\lfloor\max\{2,k+\log_2(c)\}\rfloor+1$.