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 notation

  1. Aug 11, 2014 #1

    For the following functions, what are their big-O notation?

    1. n^(n-1)
    2. (n-1)^n

    Should their big-O notations be the same as the original functions? i.e.

    1. O(n^(n-1)) = n^(n-1)?
    2. O((n-1)^n) = (n-1)^n?

    Please help!
    Many thanks!
  2. jcsd
  3. Aug 11, 2014 #2


    User Avatar
    Science Advisor

    If you look at the definition of big-O notation, it is an asymptotic inequality. Roughly speaking, f(x) = O(g(x)) whenever g grows as fast or faster than f.

    In this case, g(x) = nn grows faster than both. So it would be both convenient and correct to say that both are O(nn).

    Without more context, it is impossible to say whether this is "good enough" for your purposes.
  4. Aug 11, 2014 #3
    Thanks! I can understand that O(n^(n-1)) = n^n. But can I say O(n^(n-1)) = n^(n-1)? I am trying to find a tighter asymptotic upper bound.

    Similar to the second case.

  5. Aug 11, 2014 #4


    User Avatar
    Science Advisor

    I have a quibble with the notation you use above. It is correct to say that nn-1 = O(nn). This is not a real equality. It's just a notation. One might loosely read "=O(g)" as "is of order g". It is incorrect to say that O(nn-1) = nn. The latter notation suggests that O() is a function which returns a single function as its value.

    I can't think of any upper bounds that are both simpler than nn-1 and tighter than nn.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook