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.

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)?

Example: Prove that $x^n$ is $O(n!)$ for every real number $x$.

My proof by contradiction: If $x^n$ is $O(n!)$ then there does not exist $C$ and $K$ such that $|f(x)| \leq C|g(x)|$ whenever $x>K$. But $x^n<C(n!)$ when $C>x^n$ for all numbers, a contradiction right?

share|improve this question
    
That looks good to me... –  anorton Mar 4 '13 at 2:45
    
Sorry, that is not a proof, and it is not a question of minor missing bits. You basically need to show that for any fixed $x$, there is an $N$ and a $C$ such that $|x^n|\lt Cn!$ for every $n\gt N$. You cannot adjust the $C$ when you meet a new $n$. The same $C$ has to work for all big enough $n$. –  André Nicolas Mar 4 '13 at 2:56

1 Answer 1

up vote 3 down vote accepted

For every $x\in\mathbb{R}$, the series $$ e^x=\sum_{n\geq 0}\frac{x^n}{n!} $$ converges.

In particular, the general term tends to $0$.

So $$ \frac{x^n}{n!}=O(1)\qquad\Rightarrow \qquad x^n=O(n!). $$

Alternative (since you don't know series): set $a_n:=x^n/n!$.

Then $$ \frac{a_{n+1}}{a_{n}}=\frac{x}{n+1}\longrightarrow 0. $$ In particular, there exists $N$ such that $$ \frac{|a_{n+1}|}{|a_n|}\leq\frac{1}{2}\quad\forall n\geq N. $$ Then an easy induction shows $$ |a_n|\leq \frac{|a_N|}{2^{n-N}}\qquad \forall n\geq N. $$ Therefore, by the squeeze theorem, we have $$ \lim a_n=\lim \frac{x^n}{n!}=0. $$ In particular, the sequence $x^n/n!$ is bounded, say by $C>0$, $$ \frac{|x^n|}{n!}\leq C \quad\Rightarrow\quad |x^n|\leq Cn!\quad\forall n\geq 0. $$ The last expression reads $$ x^n=O(n!). $$

share|improve this answer
    
That looks foreign to me, we havent started series yet so im assuming we would have to give an answer without them. Are you saying C would be x^n/n! and K would be 0. This would work for all any x. –  Ddayne Mar 4 '13 at 3:56
    
@Infodayne Here is a series-free proof. –  1015 Mar 4 '13 at 4:05

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.