Big-O notation

  • Thread starter peterlam
  • Start date
  • #1
peterlam
16
0
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!
 

Answers and Replies

  • #2
jbriggs444
Science Advisor
Homework Helper
11,572
6,221
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.
 
  • Like
Likes 1 person
  • #3
peterlam
16
0
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!
 
  • #4
jbriggs444
Science Advisor
Homework Helper
11,572
6,221
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.

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.
 

Suggested for: Big-O notation

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
665
  • Last Post
Replies
5
Views
688
  • Last Post
Replies
1
Views
252
  • Last Post
Replies
3
Views
682
  • Last Post
Replies
23
Views
4K
  • Last Post
Replies
3
Views
690
Replies
11
Views
1K
  • Last Post
Replies
7
Views
780
  • Last Post
Replies
12
Views
790
Top