Associated Topics || Dr. Math Home || Search Dr. Math

```
Date: 7/5/96 at 10:8:22
From: Scott Turner

I'm trying to prove that e^n (n is a natural number) is not O(n^m) for
any power of m.  Note: e^n = 1 + n + n2/2!+ ....

I've begun by attempted that the e^n is O(n^m) in which case there is
a constant C such that e^n <= Cn^m.

Next I took the natural log of both sides, which resulted in
n <= ln C + mln N.  From there I don't think that I can say my
assumption is false but I'm stuck.

Thanks.

ST
```

```
Date: 7/8/96 at 9:42:5
From: Doctor Richard
Subject: Re: Proof by Contradiction: e^n....

Hi Scott,

That idea of taking ln of both sides was a reasonable thing to try,
but in this case it leaves you with an equivalent problem because you
need some sort of approximation of  ln(n)  in order to derive a

Instead, I think the simplest way to get this result is to compare
n^m  with n^(m   1)  and realize that the second of these must
eventually overwhelm the first, no matter what positive constants
those are multiplied by.  By "eventually", I mean for large enough n.
(Actually, to prove that  e^n  is not O(n^m), it suffices merely to
show that for any constant C > 0,  e^n > C n^m   for certain
arbitrarily high values of  n; but in this case showing it for _all_

So, do you see where I'm going?  Just observe that

n^(m + 1)/(m + 1)! < e^n

for all positive  n, because that's just one of the terms in the
series and all the terms are positive.  So if you're assuming that
e^n < C n^m  for all sufficiently large  n, we get

n^(m + 1)/(m + 1)! < C n^m

for all sufficiently large  n.   Remember that  m  here is fixed
(though arbitrary).  I think you can see how to finish getting a
contradiction from this.   So  e^n  can't be O(n^m) after all.

In a nutshell:  e^n  is a "sum of all non-negative integer powers of
n  (with coefficients)", so no single one of those powers can be the
dominant term in the sum.

-Doctor Richard,  The Math Forum
Check out our web site!
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search