Extension to sequences and asymptotic comparison notations

The case of sequences

These comparisons of growth rates naturally extend to sequences, as the integer n approaches +∞. Two new dominant terms are added to the hierarchy: the factorial n! and n^n.

Complete hierarchy: ln(n) << n^a (a > 0) << a^n (a > 1) << n! << n^n, as n approaches positive infinity.

Key results

• lim n → +∞ n^a / b^n = 0 for all b > 1 and all real numbers a.
• lim n → +∞ a^n / n! = 0 for all real numbers a.
• lim n → +∞ n! / n^n = 0.

Example

To examine lim n → +∞ (3^n)/n!, we apply the second result directly: the factorial always eventually outweighs a geometric sequence, regardless of its common ratio.

Notations o(.) and O(.)

To formalise these comparisons, we use Landau’s notations:

• u_n = o(v_n) means that u_n/v_n → 0, i.e. that u_n is negligible compared to v_n.
• $u_n = O(v_n)$ means that $u_n/v_n$ remains bounded.

Using these notations, the theorems can be rewritten as: ln(x) = o(x^n), x^n = o(e^x), and for sequences, n! = o(n^n).

A common pitfall

Do not assume that a growth rate which appears very rapid, such as 1000^n, exceeds n!. Even with an enormous factor, a geometric sequence a^n is always dominated by n! from a certain term onwards, because n! is a product of n terms which eventually exceed a.