Why is O(log(n)) coming equal to O(log(n!))?

Question

While solving the complexity of a code, I found it as O(log(n!)). I know that this can be proven equal to O(n*log(n)). However, can someone tell where this proof is going wrong?

Theorems used:

log(ab) = log(a) + log(b)
O(a+b) = O(max(a,b))

Proof

O(log(n!)) = O(log(n*(n-1)*(n-2)*...*2*1))

           = O(log(n) + log(n-1) + ... )

           = O(max(logn, log(n-1), ...))

           = O(log(n))

Can someone tell where I'm going wrong?

You should not use max in the proof cause it is not upper bound of the sum. Or only max. — Guru Stron, Jul 27 '21 at 07:26
Following your application of max, you could also prove O(n^2) = O(n), because O(n^2) = O(n + n + ... + n) = O(max(n,n,...,n)) = O(n) — derpirscher, Jul 27 '21 at 07:29
For the record, you can find a clever proof at https://stackoverflow.com/a/8118257/4607733 — logi-kal, Jul 27 '21 at 15:38

score 4 · Accepted Answer · answered Jul 27 '21 at 07:28

4

You cannot say O(log(n) + log(n-1) + ... ) = O(max(logn, log(n-1), ...))

This is only true for a constant number of summands. In your case the number depends on n.

Otherwise you could also proof

O(n)=O(1+1+1+1+1+...1) = O(max(1,1,1,...))= O(1)

answered Jul 27 '21 at 07:28

MrSmith42

9,961
6
38
49

Oh. So the addition to max rule doesn't apply in case of infinity? – Aditya Pratap Singh Jul 27 '21 at 07:39

Why is O(log(n)) coming equal to O(log(n!))?

1 Answers1