Consider the following functions as n → ∞: f₁(n) = log*(log n) f₂(n) =…
Consider the following functions as n → ∞:
f₁(n) = log*(log n)
f₂(n) = log(log*n)
f₃(n) = log(n!)
f₄(n) = (log (n))!
Arrange the functions in order of increasing asymptotic growth and write your answer as a sequence of numbers corresponding to f₁, f₂, f₃, f₄. (If the increasing order is f₁, f₃, f₂, f₄, then write the answer as 1324) _________ .
Answer: 2134 — Final ordering (in increasing asymptotic growth): 2134 Explanation: Compare f2(n) = log(log* n) and f1(n) = log*(log n). The iterated logarithm log* n grows…
Attempted by 74 students.
Show answer & explanation
Correct answer: 2134
Final ordering (in increasing asymptotic growth): 2134
Explanation:
Compare f2(n) = log(log* n) and f1(n) = log*(log n). The iterated logarithm log* n grows without bound (albeit extremely slowly), so log*(log n) is about log* n minus a constant and therefore grows faster than the logarithm of log* n. Hence log(log* n) = f2 grows slower than log*(log n) = f1.
Compare f1(n) = log*(log n) with f3(n) = log(n!). By Stirling's approximation, log(n!) ≈ n log n - n = Θ(n log n), which grows much faster than the iterated logarithm. Therefore f1 is much smaller than f3.
Compare f3(n) = log(n!) ≈ n log n with f4(n) = (log n)!. Using Stirling on (log n)!, we get (log n)! ≈ (log n)^{log n} e^{-log n} · poly(log n), which is about exp( log n · log log n - log n ). This is enormously larger than n log n (whose logarithm is ≈ log n), so (log n)! grows much faster than log(n!).
Combining the comparisons gives the increasing order: log(log* n), log*(log n), log(n!), (log n)! — corresponding to 2134.
A video solution is available for this question — log in and enroll to watch it.