1. Not finding help here? Sign up for a free 30min 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!

Computer science proving big-O definition

  1. Oct 29, 2005 #1
    I have two questions here.
    I must prove that [tex]f(n) = 100n^2 + 5n + 10[/tex] is in big-O of [tex]g(n) = n^3 - 100n^2[/tex]
    I already found a constant [tex]c[/tex] and an [tex]n[/tex] that satisfies the condition such that [tex]f(n) \leq c * g(n)[/tex]. Let [tex]c = 1[/tex] and [tex]n = 201[/tex].
    However, I am stuck on showing/manipulating the algebra that this is true.

    Second question:

    How would you prove this? I know you use the triangle inequality, but I have no idea how to implement this. Any help would be great, thanks.

    If [tex]f[/tex] in big-O of [tex]g[/tex] then [tex]|f - g|[/tex] in big-O [tex]g[/tex]
     
    Last edited: Oct 29, 2005
  2. jcsd
  3. Oct 29, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I assume you meant to say that c=1 and n=201 satisfy the condition that

    [tex]\forall m \geq n: f(m) < c * g(m)[/tex]

    Intuitively, g(n) grows faster than f(n), right? Can you think of any algebraic way to capture this notion?



    As for the other question, how far have you gotten in your attempt? Have you at least written down what you're assuming and what you're trying to prove?
     
  4. Oct 29, 2005 #3
    Hmm, I couldn't really think of an algebraic way of capturing that, but what I did was find the derivative of f and g. Then I solved for [tex]g'(n) - f'(n) = 0[/tex] and got n = 133.3 and -0.12. However, I do not know how to better show that f is less than c * g(n) for n >= 210.


    btw, I solved the |f - g| is in big-O of g
     
  5. Oct 29, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I bet you have, and just haven't realized it yet.

    Why did you solve g'(n) - f'(n) = 0 for n?
     
  6. Oct 29, 2005 #5
    Whoops, I meant that I solved for (f - g)' because we want to know when the function is >= 0 and not less than 0. Am I doing the right thing?
     
  7. Oct 29, 2005 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Probably. But if you said what you're trying to do, it might help you organize it into a proof.
     
  8. Oct 29, 2005 #7
    Alright, I will give that a try, thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Computer science proving big-O definition
  1. Big O (Replies: 7)

  2. Big-O Definition (Replies: 4)

Loading...