CODEWITHSUNDEEP
algorithmmathtime-complexitybig-o
Ayala Avraham
Ayala Avraham

Reputation: 11

Which one is bigger (loglogn)! or (log(n!))?

Need your help, stuck on this question: determine the asymptotic relation between (log(log(n)))! and (log(n!))

Upvotes: 0

Views: 363

Answers (1)

OmG
OmG

Reputation: 18838

You can use the lemma that log(n!) = Theta(n log(n)) (can be proved by Stirling approximation for n!).

Now, as the log function is increasing, you can take a log from these two functions, and finally compare them to find the relation:

# lemma: log(n*m) = log(n) + log(m)
log(log(n!)) = Theta(log(n) + log(log(n)) = Theta(log(n))

# using Stirling lemma
log(log(log(n))!) = Theta(log(log(n)) * log(log(log(n))))

As log(log(n)) * log(log(log(n))) = o(log(n)) (can be proved by taking log from these two functions: reach to log(log(log(n)) and log(log(n)).), hence, log(log(n))! = o(log(n!) (little-oh). In other words, log(log(n))! is asymptotically less than log(n!).

Upvotes: 2

Related Questions