My algorithm textbook has a theorem that says
'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.'
However, it does not provide proof.
Of course I know exponential grows faster than polynomial in most cases, but is it true for all case?
What if the polynomial function is something like $n^{100^{100}}$ and exponential is $2^n$? Will the latter outgrow the former at some point?
No comments:
Post a Comment