it is given that complexity of lg(n!) is nlogn. But if we first calculate n! with the help of a loop and then take it’s log won’t it’s complexity be O(n)?
Complexity of lg(n!)
@Akshita99
hello Akshita,
yeah in that case it will be O(n).
I think they have derived this time complexity in this way.
log(N!)= log(N * (N-1) * (N-2) * (N-3) * (N-4). . . . . . . . . . . . . . . . . . . . . . . . .3 * 2 * 1 )
by using log property i,e log(a * b) => log(a) + log(b)
Log(N!)= log(N)+log(N-1) +log(N-2) +log(N-3) +log(N-4) … … … … . .
now let say N is very big number such that N-1 ==N-2== N-3 ==N-4 ==N-K == N
log(N!)= log(N)+ Log(N)+log(N)+log(N)+log(N) … (total N terms will be there)
log(N!)=N*log(N)
Now if we say that our log function works in constant time then
Log(N!)=N
otherwise Log(N!)=nLOG(N)
so how will we know which option to choose in mcq when such question is given?
@Akshita99
see time complexity highly depends on implementation.
here they have not mentioned any thing about implementation so we cannot comment much on it.
okay thank you for your help