# Proving asymptotic relations between two functions

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 $\log n \leq C n$ for a large enough constant $C$ ? – blabler Oct 20 '12 at 3:46

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