- #1

- 16

- 0

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!

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter peterlam
- Start date

- #1

- 16

- 0

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

jbriggs444

Science Advisor

Homework Helper

- 9,955

- 4,550

In this case, g(x) = n

Without more context, it is impossible to say whether this is "good enough" for your purposes.

- #3

- 16

- 0

Similar to the second case.

Thanks!

- #4

jbriggs444

Science Advisor

Homework Helper

- 9,955

- 4,550

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 n

I can't think of any upper bounds that are both simpler than n

Share: