360 views

1 Answer

Best answer
2 votes
2 votes

We can write the following recurrence relation for f(n) = n!

T(n) = nT(n-1)
T(0) = 1

which , on expanding , will give 

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

by Stirling's approximation

{\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n},}

we can conclude n! = O(nn) . 

complexity of log(n!) is also coming from this. we have, 

{\displaystyle \ln n!=n\ln n-n+O(\ln n)}

or ln(n!) = O(ln n) .
 

selected by

Related questions

0 votes
0 votes
5 answers
1
Deepalitrapti asked Aug 27, 2018
598 views
Any condition for f(n) and g(n) or any value we can take??? I m confused becoz in big oh right side part must b greater than equal ??
3 votes
3 votes
3 answers
2
Sayan Das 1 asked Sep 21, 2016
780 views
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
Deepalitrapti asked Aug 27, 2018
287 views
Condition satisfies or not