[Math] Rate of growth of exponential functions

algorithmsasymptoticsexponential function

I have difficulties about proving the following:

Prove that exponential functions $a^n$ have different orders of growth for different
values of base $a>0$.

It looks obvious that when $a=3$ it grows faster when compared to $a=2$. But how do i make a formal proof for this? Thanks for your help.

Best Answer

Here's a sketch of a proof: suppose $a,b>0$, and $a\neq b$. Without loss of generality, $a>b$. We want to show that $O(a^n)\neq O(b^n)$, or equivalently, that $a^n\notin O(b^n)$ (why are these equivalent?)

To show that $a^n\notin O(b^n)$, it suffices to show (again, why?) that

$$ \lim_{n\rightarrow\infty}\frac{a^n}{b^n}=\infty $$ Using the fact that $a>b>0$, this limit should be easy to show.