Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.