# Proving a function is big O

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?

-
That looks good to me... –  apnorton 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

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!).$$

-
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