CODEWITHSUNDEEP
time-complexity
S. Kraw
S. Kraw

Reputation: 33

What is the performance of log(n!) compared to n?

I was wondering if log(n!) is O(n), or if n is O(log(n!)). I have seen that log(n!) is O(n log(n)) but there is no information that I can find available to my particular question.

Upvotes: 2

Views: 138

Answers (2)

Nate Eldredge
Nate Eldredge

Reputation: 58613

Stirling's approximation implies that log(n!) = Θ(n log(n)). In particular, it is not true that log(n!) = O(n), and it is true that n = O(log(n!)).

Upvotes: 2

taurus05
taurus05

Reputation: 2546

Log(n!) grows much faster as compared to n. You can see from the picture. Example : When n =50, O(n) will be 50. But, O(log(n!)) = 64.48.Graph

Update :

I tried plotting n and log(n!), on the same Graph.Log(n!) vs n Graph

log(n!) = O(n) for 0 < n < 25 
n = O(log(n!)) for n > 25

Upvotes: 1

Related Questions