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