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!

Big O

  1. Oct 1, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that f(n) = n * log (n) is O(n(1+sqrt(n))).

    2. Relevant equations
    n/a


    3. The attempt at a solution
    I really don't know what to do else I wouldn't be here :? Some hints would be appreciated!
     
  2. jcsd
  3. Oct 1, 2007 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Definitions are usually a good place to start.
     
  4. Oct 1, 2007 #3
    f(n) is O(g(n)) if and only if there exists an n_0 part of natural numbers and a constant C that is part of rational numbers for which f(n) <= that c*g(n) for all n >= n_o

    I know the def just don't know how to get g(n)...
     
  5. Oct 1, 2007 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, you were given an f(n) and asked to prove
    f(n) is O(n(1+sqrt(n))),​
    weren't you? ...
     
  6. Oct 1, 2007 #5
    yes well I don't know how to go from f(n) to g(n)... the examples I have seen were just that you would multiply so part of f(n) until you could group everything together to get c* g(n) but this time I don't see how I can multiply anything to get anything that looks like g(n)...
     
  7. Oct 1, 2007 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think I had misunderstood you -- your last post sounded like you said you didn't know what g(n) was.

    Did you try solving for c? What did you get?
     
  8. Oct 2, 2007 #7
    I don't know where to start to solve for c.. that is my problem...

    I don't understand where the 1 comes from... I know O(logn) < O(sqrt(n)) so I can get that but where is the (1+srt(n)) comes from?
     
    Last edited: Oct 2, 2007
  9. Oct 2, 2007 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Well, assuming that the problem is correct, you have a known f(n) and g(n) in the inequality
    f(n)< C g(n)

    I think you can handle solving that for C.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Big O
  1. Big O analysis (Replies: 1)

  2. Big-O Definition (Replies: 4)

Loading...