I am trying to find the big-oh notation of

T(n)=n*T(n-1)

where T(1)=1 is the answer O(n!) or O(n^n)?

CodePudding user response：

As Big-O notation technically defines sets of functions, and upper bounds on those sets, it is worth noting that both are technically correct.

A closer, tighter upper bound on the recurrence relation is

O(n!)

since

n!  = 1 * 2 * ... * n
n^n = n * n * ... * n

clearly shows that n^n is larger than n!.

You can prove this by induction as well.

Since T(n 1) = (n 1) * T(n) which is equal to (n 1)! since you can assume T(n) = n!.

CodePudding user response：

T(n) = n!

Then you get theta(n!).

Omega(n!) is correct

omega(n!) is not correct

Theta(n!) is correct

o(n!) is not correct

O(n!) is correct

o(n^n) is correct

O(n^n) is correct