Which function is asymptotically larger between n and log(n!)

Question

I guess O(log(n!)) is asymptotically slower than O(n). Am I right ?

Look up Stirling's formula, it answers this question. – Nate Eldredge Sep 16 '21 at 16:56 — Nate Eldredge, Sep 16 '21 at 16:56

score 1 · Answer 1 · answered Sep 16 '21 at 17:01

1

Unfortunately, your guess is completely wrong! try to expand log(n!) as the following:

log(n!) = log(n * (n-1) * ... * 1) > log(n * (n-1) * ... * n/2) > 
log((n/2)^n) = n log(n/2) \in Theta(n log(n))`

Therefore, n \in O(log(n!))

answered Sep 16 '21 at 17:01

OmG

@CharanShetty Definitely, the growth of `n log n` is faster than `n`. Is it clear for you? – OmG Sep 16 '21 at 17:10
Yes, `n log n` will have faster growth than `n` – Charan Shetty Sep 16 '21 at 17:12

1 Answers1