SKEDSOFT

Factorials: The notation n! (read "n factorial") is defined for integers n ≥ 0 as

Thus, n! = 1 · 2 · 3 n.

A weak upper bound on the factorial function is n! ≤ nⁿ, since each of the n terms in the factorial product is at most n. Stirling's approximation,

where e is the base of the natural logarithm, gives us a tighter upper bound, and a lower bound as well

where Stirling's approximation is helpful in proving equation (3.18). The following equation also holds for all n ≥ 1:

Functional iteration: We use the notation f⁽ⁱ⁾(n) to denote the function f(n) iteratively applied i times to an initial value of n. Formally, let f(n) be a function over the reals. For nonnegative integers i, we recursively define

For example, if f(n) = 2n, then f⁽ⁱ⁾(n) = 2ⁱn.

The iterated logarithm function: We use the notation lg* n (read "log star of n") to denote the iterated logarithm, which is defined as follows. Let lg⁽ⁱ⁾ n be as defined above, with f(n) = lg n. Because the logarithm of a nonpositive number is undefined, lg⁽ⁱ⁾ n is defined only if lg^(i-1) n > 0. Be sure to distinguish lg⁽ⁱ⁾ n (the logarithm function applied i times in succession, starting with argument n) from lgⁱ n (the logarithm of n raised to the ith power). The iterated logarithm function is defined as

lg* n = min {i = 0: lg⁽ⁱ⁾ n ≤ 1}.

The iterated logarithm is a very slowly growing function:

Since the number of atoms in the observable universe is estimated to be about 10⁸⁰, which is much less than 2⁶⁵⁵³⁶, we rarely encounter an input size n such that lg* n > 5.