lg (n!) = ………………
a) O(n)
b) O(lg n)
c) O(n^2)
d) O(n lg n)
Answer is d) O(n lgn)
please explain…
lg (n!) = ………………
a) O(n)
b) O(lg n)
c) O(n^2)
d) O(n lg n)
Answer is d) O(n lgn)
please explain…
n! = n * (n - 1) * (n - 2) * (n - 3) ... 2 * 1
log(n!) = log(n * (n - 1) * (n - 2) * (n - 3) ... 2 * 1)
log(n!) = log(n) + log(n - 1) + log(n - 2) + ... + log(2) + log(1)
log(n!) = O(log(n) + log(n) + log(n) + ... log(n) + log(n))
log(n!) = O(n*log(n))