0
$\begingroup$

Is $n^a \in O(b^n)$, where $O(\ast)$ represents asymptotic notation? We only requre $a \in \mathbb R$ and $b > 1$.

Would appreciate the help! Thanks.

  • 0
    @blabler $C=1$ is usually pretty small, assuming the natural base.2017-04-30

1 Answers 1

0

$b^n = e^{n \log_e(b)} = \sum_{k=0}^{\infty} \dfrac{(n \log_e(b))^k}{k!}$ Let $m = \lceil a \rceil$. We then have $b^n = \sum_{k=0}^{\infty} \dfrac{(n \log_e(b))^k}{k!} \geq \dfrac{(n \log_e(b))^m}{m!}$ Hence, $n^a \leq n^m \leq \dfrac{m!}{\log^m_e(b)} b^n$