Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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

 
discard

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.