# Rate of growth of exponential functions

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.

-
add comment

## 1 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.

-
Thanks for the help, just a little question: Does it suffice to show this for big-o notation? Do i need to show the same thing for big omega case, or this is enough? @icurays1 –  bigO Feb 23 '13 at 19:30
Showing $a^n\notin O(b^n)$ would be the same as showing $b^n\notin \Omega(a^n)$ (big Omega is the "inverse" of big oh). –  icurays1 Feb 23 '13 at 19:57
add comment