Page 2 of 2 FirstFirst 12
Results 16 to 23 of 23

Math Help - Big O - Explanation needed

  1. #16
    Newbie
    Joined
    Aug 2009
    Posts
    8

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by Roclemir View Post
    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 x\rightarrow \infty. For large x (in particular x>1) we have:

    |\frac{4x^3-3x^2+1}{x^3}| =\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 \sum sign up there in the top right and type your equations in side the math tags. It reads LaTeX
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Newbie
    Joined
    Aug 2009
    Posts
    8

    proof

    and that's considered proof?
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    That is the definition of big O, I dunno what else you are looking for.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Newbie
    Joined
    Aug 2009
    Posts
    8

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Newbie
    Joined
    Aug 2009
    Posts
    8

    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
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by Roclemir View Post
    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 f(x)=O(x^3). Like you can just look at f(x) and know that it is O(x^3).

    Any polynomial p(x) of degree n is always O(x^n). You can use this same method to see that 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 x_0 for which |f(x)|\leq M |g(x)| for all 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 |f(x)|\leq 8|x^3| so by definition f(x)=O(x^3).
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Quote Originally Posted by Roclemir View Post
    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 \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.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Permutation Tensor (Explanation Needed)
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: September 14th 2011, 05:37 AM
  2. Explanation needed on a sequence proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: June 2nd 2011, 12:30 PM
  3. Function of F(X) Explanation needed.
    Posted in the Algebra Forum
    Replies: 7
    Last Post: January 13th 2011, 11:08 AM
  4. Algebra Explanation Needed
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 31st 2010, 02:55 AM
  5. Multiplication explanation needed
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 7th 2009, 10:46 AM

Search Tags


/mathhelpforum @mathhelpforum