1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big-O Definition

  1. Oct 28, 2013 #1
    1. The problem statement, all variables and given/known data
    Let [itex]f(x) = 2x^{3} + 3x\log{x}[/itex], prove [itex]f \in O(x^{3})[/itex] using the Big-O Definition.

    2. Relevant equations
    Big-O definition:
    [itex]f(x) \in O(g(x))[/itex] if [itex]|f(x)| \leq C|g(x)|[/itex] and [itex]x \geq k[/itex] where [itex]C[/itex] and [itex]k[/itex] are both positive integers.

    3. The attempt at a solution
    I basically set [itex]C=4[/itex] and [itex]k=4[/itex], then wrote it out:
    [itex]|2x^{3}+3x\log{x}| \leq 4|x^{3}|[/itex] where [itex]x \geq 4[/itex]

    then using 4 for x:
    [itex]256 \geq 152[/itex]

    According to the definition this proves it. It just seems to simple for an assignment (not the only problem on it, but still). Did I prove this correctly? Or do I completely not understand? I can prove it using limits, but she wants us to use the Big-O therom.
     
  2. jcsd
  3. Oct 28, 2013 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You have to prove it for EVERY x larger than 4, not just when x = 4. Also is your log base 2?
     
  4. Oct 28, 2013 #3

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    So saying ##|2x^{3}+3x\log{x}| \leq 4|x^{3}|## when ##x>4## you are observing that ##3x\log x \le 2x^3## when ##x\ge 4##. I would think you would need to give an argument for that or at least explain why you already know that after checking ##x=4##.
     
  5. Oct 28, 2013 #4
    Yes, the log base is assumed to be 2. Sorry, I forgot about that.

    Hmm, I guess I don't understand that technique then. I can do it using limits, but I guess I'll just have to review it until I get it.
     
  6. Oct 28, 2013 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's just an ordinary calculus question now. How could you argue that ##3x\log_2 x \le 2x^3## if ##x>4##?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Big-O Definition
  1. Big O (Replies: 7)

Loading...