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? Please help! Many thanks!
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) = n^{n} grows faster than both. So it would be both convenient and correct to say that both are O(n^{n}). Without more context, it is impossible to say whether this is "good enough" for your purposes.
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!
I have a quibble with the notation you use above. It is correct to say that n^{n-1} = O(n^{n}). 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(n^{n-1}) = n^{n}. 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 n^{n-1} and tighter than n^{n}.