Polynomial versus exponential growth
= Polynomial versus exponential growth
{title2=$n^k=o(a^n)\quad(a>1)$}
Every fixed power is eventually smaller than an <exponential function> with base $a>1$: for a fixed nonnegative integer $k$, $n^k/a^n\to0$. To prove this, the ratio of successive terms is $(1+1/n)^k/a\to1/a<1$, so after finitely many terms the ratio is bounded by a fixed $q<1$. A <geometric series> bound then proves the limit. In particular $n^k=O(a^n)$ in <big O notation>.