Disproving Big-oh

Question

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.

No actually. But if I were to prove it, how would I pick values for k and c that do not depend on n? — RandomDude_123, Mar 05 '19 at 01:27
Is the statement you are trying to disprove $\exists k$ such that $\forall n$ $n^{n} \in O(n^{k})$ or is it $\forall n$ $\exists k$ such that $n^{n} \in O(n^{k})$? — Boots, Mar 05 '19 at 01:35

score 0 · Accepted Answer · answered Mar 05 '19 at 01:51

0

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$.

answered Mar 05 '19 at 01:51

SmileyCraft

6,777
13
26

Disproving Big-oh

1 Answers1