Monotonicity

A function f(n) is monotonically increasing if m ≤ n implies f(m) ≤ f(n). Similarly, it is monotonically decreasing if m ≤ n implies f(m) ≥ f(n). A function f(n) is strictly increasing if m < n implies f(m) < f(n) and strictly decreasing if m < n implies f(m) > f(n).

Floors and ceilings

For any real number x, we denote the greatest integer less than or equal to x by ⌊x⌋ (read "the floor of x") and the least integer greater than or equal to x by ⌈x⌉ (read "the ceiling of x"). For all real x,

For any integer n,

⌈n/2⌉ + ⌊n/2⌋ = n,

and for any real number n ≥ 0 and integers a, b > 0,

The floor function f(x) = ⌊x⌋ is monotonically increasing, as is the ceiling function f(x) = ⌈x⌉.

Modular arithmetic

For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a/n:

Given a well-defined notion of the remainder of one integer when divided by another, it is convenient to provide special notation to indicate equality of remainders. If (a mod n) = (b mod n), we write a ≡ b (mod n) and say that a is equivalent to b, modulo n. In other words, a ≡ b (mod n) if a and b have the same remainder when divided by n. Equivalently, a ≡ b (mod n) if and only if n is a divisor of b - a. We write a ≢ b (mod n) if a is not equivalent to b, modulo n.

Polynomials

Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form

where the constants a₀, a₁, ..., a_d are the coefficients of the polynomial and a_d ≠ 0. A polynomial is asymptotically positive if and only if a_d > 0. For an asymptotically positive polynomial p(n) of degree d, we have p(n) = Θ(n^d). For any real constant a ≥ 0, the function n^a is monotonically increasing, and for any real constant a ≤ 0, the function n^a is monotonically decreasing. We say that a function f(n) is polynomially bounded if f(n) = O(n^k) for some constant k.

Exponentials

For all real a > 0, m, and n, we have the following identities:

For all n and a ≥ 1, the function aⁿ is monotonically increasing in n. When convenient, we shall assume 0⁰ = 1.

The rates of growth of polynomials and exponentials can be related by the following fact. For all real constants a and b such that a > 1,

from which we can conclude that

n^b = o(aⁿ).

Thus, any exponential function with a base strictly greater than 1 grows faster than any polynomial function.

Using e to denote 2.71828..., the base of the natural logarithm function, we have for all real x,

where "!" denotes the factorial function defined later in this section. For all real x, we have the inequality

where equality holds only when x = 0. When |x| ≤ 1, we have the approximation

When x → 0, the approximation of e^x by 1 + x is quite good:

e^x = 1 + x + Θ(x²).

(In this equation, the asymptotic notation is used to describe the limiting behavior as x → 0 rather than as x → ∞.) We have for all x,

Logarithms

We shall use the following notations:

An important notational convention we shall adopt is that logarithm functions will apply only to the next term in the formula, so that lg n + k will mean (lg n) + k and not lg(n + k). If we hold b > 1 constant, then for n > 0, the function log_b n is strictly increasing.

For all real a > 0, b > 0, c > 0, and n,

where, in each equation above, logarithm bases are not 1.

By equation (3.14), changing the base of a logarithm from one constant to another only changes the value of the logarithm by a constant factor, and so we shall often use the notation "lg n" when we don't care about constant factors, such as in O-notation. Computer scientists find 2 to be the most natural base for logarithms because so many algorithms and data structures involve splitting a problem into two parts.

There is a simple series expansion for ln(1 + x) when |x| < 1:

We also have the following inequalities for x > -1:

where equality holds only for x = 0.

We say that a function f(n) is polylogarithmically bounded if f(n) = O(lg^k n) for some constant k. We can relate the growth of polynomials and polylogarithms by substituting lg n for n and 2^a for a in equation (3.9), yielding

From this limit, we can conclude that

lg^b n = o(n^a)

for any constant a > 0. Thus, any positive polynomial function grows faster than any polylogarithmic function.

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. One can prove (see Exercise 3.2-3)

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

where

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.

Fibonacci numbers

The Fibonacci numbers are defined by the following recurrence:

Thus, each Fibonacci number is the sum of the two previous ones, yielding the sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .

Fibonacci numbers are related to the golden ratio φ and to its conjugate , which are given by the following formulas:

Specifically, we have

which can be proved by induction (Exercise 3.2-6). Since , we have , so that the ith Fibonacci number F_i is equal to rounded to the nearest integer. Thus, Fibonacci numbers grow exponentially.