Which of the following is asymptotically smaller ?

Key insight: compare the growth rates: iterated logarithm (log*) grows much more slowly than ordinary logarithms, and logarithm of factorial grows very fast (Θ(n log n)).

Interpretation of the functions:

• lg(lg n): the double logarithm, which grows slowly but unbounded.

• lg*(lg n): the iterated logarithm applied to log n. Note that lg*(lg n) ≈ lg*(n) − 1, so it grows even more slowly than lg*(n).

• lg(n!): by Stirling's approximation, lg(n!) = Θ(n lg n), which grows much faster than any logarithmic or iterated-logarithmic function.

• lg*(n!): iterated logarithm of n! is within a constant of lg*(n) for large n, so it grows like lg*(n).

Ordering from smallest to largest (for sufficiently large n):

• lg*(lg n) (smallest) — grows slower than lg*(n).

• lg*(n!) ≈ lg*(n) — slightly larger than lg*(lg n), but still extremely slow.

• lg(lg n) — larger than iterated-logarithm functions for very large n.

• lg(n!) = Θ(n lg n) (largest) — grows polynomially times logarithm.

Conclusion: the asymptotically smallest function among the choices is lg*(lg n).