Standard Notations And Common Functions
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! ≤ nn, 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(i)(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(i)(n) = 2in.
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(i) n be as defined above, with f(n) = lg n. Because the logarithm of a nonpositive number is undefined, lg(i) n is defined only if lg(i-1) n > 0. Be sure to distinguish lg(i) n (the logarithm function applied i times in succession, starting with argument n) from lgi n (the logarithm of n raised to the ith power). The iterated logarithm function is defined as
lg* n = min {i = 0: lg(i) n ≤ 1}.
The iterated logarithm is a very slowly growing function:
lg* 2 |
= |
1, |
lg* 4 |
= |
2, |
lg* 16 |
= |
3, |
lg* 65536 |
= |
4, |
lg*(265536) |
= |
5. |
Since the number of atoms in the observable universe is estimated to be about 1080, which is much less than 265536, we rarely encounter an input size n such that lg* n > 5.