# Thread: Big O - Explanation needed

1. ## Something isn't clicking in my head

I've read all your posts, and reread them and there's something just no quite clicking. I need to prove, from first principals (which i'm not sure what first principles are), that:

f(x) = O(x^3) when given

f(x)=4x^3 - 3x^2 + 1

is this equivelant of the above equation or am i barking up the wrong post here?

p.s. and how do you get the superscript and subscript to work in these posts?

2. Originally Posted by Roclemir
I've read all your posts, and reread them and there's something just no quite clicking. I need to prove, from first principals (which i'm not sure what first principles are), that:

f(x) = O(x^3) when given

f(x)=4x^3 - 3x^2 + 1

is this equivelant of the above equation or am i barking up the wrong post here?

p.s. and how do you get the superscript and subscript to work in these posts?
You just gotta show that when you divide f(x) by what you claim it is big 'Oh' of it is bounded when you take the limit as $\displaystyle x\rightarrow \infty$. For large x (in particular x>1) we have:

$\displaystyle |\frac{4x^3-3x^2+1}{x^3}|$$\displaystyle =\frac{|4x^3-3x^2+1|}{|x^3|}\leq \frac{|4x^3|+|3x^2|+|1|}{|x^3|}\leq \frac{4|x^3|+3|x^3|+1|x^3|}{|x^3|}\leq \frac{8x^3}{x^3}=8$

So clearly this limit is bounded.

To get math stuff to work hit the $\displaystyle \sum$ sign up there in the top right and type your equations in side the math tags. It reads LaTeX

3. ## proof

and that's considered proof?

4. That is the definition of big O, I dunno what else you are looking for.

5. ## one last thing

Ok. Thanks for that. The original question says "Prove from first principles". Is this what we have done here?

if so, What exactly are the first principles? or is it just another way of saying use the big O?

6. ## Think i get it

I think i get it
Big O is using inequalities to make like terms and breaking it down so that we get a constant.
Just need to know what the first principles are now

7. Originally Posted by Roclemir
I think i get it
Big O is using inequalities to make like terms and breaking it down so that we get a constant.
Just need to know what the first principles are now
First principles is one of those ambiguous terms that is kind of up to author/grader/reader to decide exactly what it means. Generally it refers to prove the thing from definitions and/or axioms that have been given. In this case I think the author wants you to actually show that this limit is bounded, and not just say it $\displaystyle f(x)=O(x^3)$. Like you can just look at f(x) and know that it is $\displaystyle O(x^3)$.

Any polynomial p(x) of degree n is always O(x^n). You can use this same method to see that $\displaystyle p(x)\leq p(1)x^n$. Notice p(1) is just the sum of all of the coefficients of p(x). They probably wanted you to actually write out the steps is what the author meant.

It is possible that they actually would like you to prove this limit is bounded. That is there exists a number M and an x value $\displaystyle x_0$ for which $\displaystyle |f(x)|\leq M |g(x)|$ for all $\displaystyle x>x_0$. But this amounts to doing precisely the same thing I did, notice the M i chose was 8 and as long as x>1 this inequality holds and therefore $\displaystyle |f(x)|\leq 8|x^3|$ so by definition $\displaystyle f(x)=O(x^3)$.

8. Originally Posted by Roclemir
I think i get it
Big O is using inequalities to make like terms and breaking it down so that we get a constant.
Just need to know what the first principles are now
Kind of, yeah when f(x) is Big O of g(x), it just means their ratio $\displaystyle \frac{f(x)}{g(x)}$ is bounded by some real number eventually. There may be some places early on where the ratios are not bounded, but it just is important that eventually this ratio becomes bounded. Any time when you are dealing with bounds there will be inequalities involved. The nice thing about this is that the bounds don't have to be good bounds just any bound is sufficient to show big O.

Page 2 of 2 First 12