Which of the following functions is asymptotically smallest as n grows without…

Concept

Asymptotic comparison asks how functions behave as n grows without bound. If f(n)/g(n) tends to 0, then f is asymptotically smaller than g.

The iterated logarithm lg* n is the number of repeated logarithms needed to reduce n to at most 1. It grows without bound, but extraordinarily slowly; for every unbounded positive x, lg x = o(x).

Application

1. Here lg* denotes the iterated logarithm, so lg(lg*n) is read as lg(lg* n).

2. Let m = lg* n. Then m tends to infinity and lg(lg* n) = lg m.

3. Starting with lg n completes one logarithm step, so for sufficiently large n, lg*(lg n) = lg* n − 1 = m − 1, which has order Θ(m).

4. By Stirling's formula, lg(n!) = Θ(n lg n), so it grows far faster than logarithmic and iterated-logarithmic expressions.

5. Because lg(n!) = Θ(n lg n), repeated logarithms reduce n! to the same scale as n after only a constant number of extra steps. Hence lg*(n!) = m + O(1), which has order Θ(m).

Cross-check

The ratio lg m/(m − 1) tends to 0. Also, lg*(n!) has order Θ(m), while lg(n!) has order Θ(n lg n), so lg m is asymptotically smaller than each of them.

Result

Therefore, the asymptotically smallest function is lg(lg* n).