# Big-O notation

Hi!

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?

Many thanks!

jbriggs444
Homework Helper
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.

1 person
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.

Thanks!

jbriggs444