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 Notation, and reading comprehension

  1. Mar 2, 2008 #1
    1. The problem statement, all variables and given/known data
    These are some problems I need to solve. Do not solve them for me. I ask two things from you:

    1) Explain what the question is asking from me, as I'm a little unclear on this.
    2) Using a completely unrelated example, or whichever not-doing-it-for-me method you wish, give a hint as to how I might actually be able to do these.

    Question 1: Find the least integer n such that f(x) is O(x^n) for each of these functions.
    a) f(x) = 2x^2 + x^3 * log(x)
    b) f(x) = 3x^5 + (log(x))^4
    c) f(x) = (x^4 + x^2 + 1) / (x^4 + 1)
    d) f(x) = (x^3 + 5log(x)) / (x^4 + 1)

    Question 2: Give a big-O estimate for each of these functions. For the function g in your estimate that f(x) is O(g(x)), use a simple function g of the smallest order.
    a) nlog(n^2 + 1) + n^2 * log(n)
    b) (nlog(n) + 1)^2 + (log(n) + 1)(n^2 + 1)
    c) n^(2^n) + n^(n^2)

    2. Relevant equations
    1, logn, n, nlogn, n^2, 2^n and n! are the "often used" terms.

    3. The attempt at a solution
    I read the textbook. My problem might be as simple as not understanding what they're asking, but totally knowing how to do it, or maybe I don't understand it anyway... I can't really gauge that until I figure out what they want :P
    Last edited: Mar 2, 2008
  2. jcsd
  3. Mar 2, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi Goldenwind!

    x^7, for example, is O(x^8) and O(x^9), but not O(x^7) or O(x^6) or …

    So 8 is the least integer for which x^7 is O(x^n).

    (warning! warning! I may have got this completely wrong, because I can't remember the definition of O() off-hand - but I hope you see what I'm getting at. :redface:)
  4. Mar 2, 2008 #3


    User Avatar
    Science Advisor

    Slightly wrong, tiny-tim, according to what I know as the "usual definition". "f= O(g)" means that the limit (as x goes to infinity) of f/g exists and is non-zero. Neither x7= O(x8) nor x7 x9) is correct but x7= O(x7).

    You are thinking of "small o"- f= o(g) means that the limit of f/g is 0. It is true that x7= o(x8 and x7= o(x9) but x7 is not o(x7).

    Those are "usual definitions". Having typed all that, I noticed that the problem said "the smallest n such that". The "O" definition above clearly gives at most a single n for each function- it may well be true that the problem is talking about "o", not "O". And perhaps Goldenwind typed "O" rather than "o" without realizing it. Goldenwind, can you check on that?

    For example, with problem (a), f(x)= x2+ x3ln(x). Since 3> 2, x2+ x3 would be O(x3) because (x2+ x3)/x3= 1/x+ 1 which goes to 1 as x goes to infinity. It would be o(x4 or any higher power of n, because (x2+ x3)/xn= 1/xn-2+ 1/xn-1 which goes to 0 for any n> 3.

    However, since ln(x) goes to infinity, but ln(x)/x goes to 0, x2+ x3ln(x) is not O(xn) for any integer n but is o(xn for any n higher than 3.
  5. Mar 2, 2008 #4
    Nope, 'tis Big-O =/

    Also, haven't a clue what you mean with limits :P
    All I know is Big-O means that f(x) <= C*g(x) when x > k, for some C,k.

    /boggle XD
  6. Mar 2, 2008 #5
    That definition means that f(x) = O(g(x)). Now, for f(x) = 2x^2 + x^3 * log(x), you want to find the least n such that 2x^2 + x^3 * log(x) <= Cx^n when x > k for some C and k. Can you find the least n now?
  7. Mar 2, 2008 #6
    I now understand what is being asked of me.
    When n = 3, Cx^3 grows faster than 2x^2... and log(x) will dampen the effectiveness of x^3, so technically x^3 > x^3*log(x)...

    ...so for that one, n=3 would be the smallest?
    Am I on the right track?
  8. Mar 2, 2008 #7
    Actually, would x^2 grow faster than x^3*log(x)?
    'cause x^3 is bigger than x^2, but log(x) is a serious dampener...

    Edit: Got it now! ^^;
    Thanks :)

    I know how to solve all of the first question now.
    And I also get what the second question is asking.
    Last edited: Mar 2, 2008
  9. Mar 3, 2008 #8
    In the first question, we were given x^n, and told to solve for n.
    In the second question, we aren't given any function, but are just told to find the Big-O.

    How do I know which function g(x) is, to compare to f(x)?
  10. Mar 3, 2008 #9
    No. log(x) doesn't "dampen the effectiveness" of x3. Your intuition is wrong. Pick a large value of x, say 1000, and tell me which one is greater: x3 or x3log x.

    Again, your intuition is wrong. Let x = 1000 and compare the two.

    You're told to find a simple function g (e.g. xn) of the smallest order. Let's look at the first one: nlog(n2 + 1) + n2 * log(n). First start by determining which of the two terms grows faster.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook