The order of growth of the running time of an algorithm, defined in Chapter 1, gives a simple characterization of the algorithm's efficiency and also allows us to compare the relative performance of alternative algorithms. Once the input size n becomes large enough, merge sort, with its 
(n lg n) worst-case running time, beats insertion sort, whose worst-case running time is (n2). Although we can sometimes determine the exact running time of an algorithm, as we did for insertion sort in Chapter 1, the extra precision is not usually worth the effort of computing it. For large enough inputs, the multiplicative constants and lower-order terms of an exact running time are dominated by the effects of the input size itself.
When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms. That is, we are concerned with how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound. Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.
This chapter gives several standard methods for simplifying the asymptotic analysis of algorithms. The next section begins by defining several types of "asymptotic notation," of which we have already seen an example in -notation. Several notational conventions used throughout this book are then presented, and finally we review the behavior of functions that commonly arise in the analysis of algorithms.
The notations we use to describe the asymptotic running time of an algorithm are defined in terms of functions whose domains are the set of natural numbers N = {0, 1, 2, . . .}. Such notations are convenient for describing the worst-case running-time function T(n), which is usually defined only on integer input sizes. It is sometimes convenient, however, to abuse asymptotic notation in a variety of ways. For example, the notation is easily extended to the domain of real numbers or, alternatively, restricted to a subset of the natural numbers. It is important, however, to understand the precise meaning of the notation so that when it is abused, it is not misused. This section defines the basic asymptotic notations and also introduces some common abuses.
In Chapter 1, we found that the worst-case running time of insertion sort is T(n) =
0
A function â(n) belongs to the set
Figure 2.1 (a) gives an intuitive picture of functions â(n) and g(n), where â(n) =
The definition of
In Chapter 1, we introduced an informal notion of
for all n
The right-hand inequality can be made to hold for any value of n
We can also use the formal definition to verify that 6n3
Intuitively, the lower-order terms of an asymptotically positive function can be ignored in determining asymptotically tight bounds because they are insignificant for large n. A tiny fraction of the highest-order term is enough to dominate the lower-order terms. Thus, setting c1 to a value that is slightly smaller than the coefficient of the highest-order term and setting c2 to a value that is slightly larger permits the inequalities in the definition of
As an example, consider any quadratic function â(n) = an2 + bn + c, where a, b, and c are constants and a > 0. Throwing away the lower-order terms and ignoring the constant yields â(n) =
Since any constant is a degree-0 polynomial, we can express any constant function as
1The real problem is that our ordinary notation for functions does not distinguish functions from values. In
The
O(g(n)) = {â(n) : there exist positive constants c and n0 such that
0
We use O-notation to give an upper bound on a function, to within a constant factor. Figure 2.1 (b) shows the intuition behind O-notation. For all values n to the right of n0, the value of the function â(n) is on or below g(n).
To indicate that a function â(n) is a member of O(g(n)), we writeâ(n) = O(g(n)). Note that â(n) =
Some readers who have seen O-notation before may find it strange that we should write, for example, n = O(n2). In the literature, O-notation is sometimes used informally to describe asymptotically tight bounds, that is, what we have defined using
Using O-notation, we can often describe the running time of an algorithm merely by inspecting the algorithm's overall structure. For example, the doubly nested loop structure of the insertion sort algorithm from Chapter 1 immediately yields an O(n2) upper bound on the worst-case running time: the cost of the inner loop is bounded from above by O(1) (constant), the indices i and j are both at most n, and the inner loop is executed at most once for each of the n2 pairs of values for i and j.
Since O-notation describes an upper bound, when we use it to bound the worst-case running time of an algorithm, by implication we also bound the running time of the algorithm on arbitrary inputs as well. Thus, the O(n2) bound on worst-case running time of insertion sort also applies to its running time on every input. The
Technically, it is an abuse to say that the running time of insertion sort is O(n2), since for a given n, the actual running time depends on the particular input of size n. That is, the running time is not really a function of n. What we mean when we say "the running time is O(n2)" is that the worst-case running time (which is a function of n) is O(n2), or equivalently, no matter what particular input of size n is chosen for each value of n, the running time on that set of inputs is O(n2).
Just as O-notation provides an asymptotic upper bound on a function,
0
The intuition behind
From the definitions of the asymptotic notations we have seen thus far, it is easy to prove the following important theorem (see Exercise 2.1-5).
Theorem 2.1
For any two functions f(n) and g(n), f(n) =
As an example of the application of this theorem, our proof that an2 + bn + c =
Since
The running time of insertion sort therefore falls between
We have already seen how asymptotic notation can be used within mathematical formulas. For example, in introducing O-notation, we wrote "n = O(n2)." We might also write 2n2 + 3n + 1 = 2n2 +
When the asymptotic notation stands alone on the right-hand side of an equation, as in n = O(n2), we have already defined the equal sign to mean set membership: n
Using asymptotic notation in this manner can help eliminate inessential detail and clutter in an equation. For example, in Chapter I we expressed the worst-case running time of merge sort as the recurrence
If we are interested only in the asymptotic behavior of T(n), there is no point in specifying all the lower-order terms exactly; they are all understood to be included in the anonymous function denoted by the term
The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears. For example, in the expression
there is only a single anonymous function (a function of i). This expression is thus not the same as O(1) + O(2) +
In some cases, asymptotic notation appears on the left-hand side of an equation, as in
We interpret such equations using the following rule: No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid. Thus, the meaning of our example is that for any function
A number of such relationships can be chained together, as in
We can interpret each equation separately by the rule above. The first equation says that there is some function
The asymptotic upper bound provided by O-notation may or may not be asymptotically tight. The bound 2n2 = O(n2) is asymptotically tight, but the bound 2n = O(n2) is not. We use o-notation to denote an upper bound that is not asymptotically tight. We formally define o(g(n)) ("little-oh of g of n") as the set
o(g(n)) = {
n0 > 0 such that 0
For example, 2n = o(n2), but 2n2
The definitions of O-notation and o-notation are similar. The main difference is that in
Some authors use this limit as a definition of the o-notation; the definition in this book also restricts the anonymous functions to be asymptotically nonnegative.
By analogy,
Formally, however, we define
n0 > 0 such that 0
For example, n2/2 =
if the limit exists. That is,
Many of the relational properties of real numbers apply to asymptotic comparisons as well. For the following, assume that
Transitivity:
Reflexivity:
Symmetry:
Transpose symmetry:
Because these properties hold for asymptotic notations, one can draw an analogy between the asymptotic comparison of two functions f and g and the comparison of two real numbers a and b:
One property of real numbers, however, does not carry over to asymptotic notation:
Trichotomy: For any two real numbers a and b, exactly one of the following must hold: a < b, a = b, or a > b.
Although any two real numbers can be compared, not all functions are asymptotically comparable. That is, for two functions
2.1-1
Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of
2.1-2
Show that for any real constants a and b, where b > 0,
2.1-3
Explain why the statement, "The running time of algorithm A is at least O(n2)," is content-free.
2.1-4
Is 2n+1 = O(2n)? Is 22n = O(2n)?
2.1-5
Prove Theorem 2.1.
2.1-6
Prove that the running time of an algorithm is
2.1-7
Prove that o(g(n))
2.1-8
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions
O(g(n, m)) = {
such that 0
for all n
Give corresponding definitions for
This section reviews some standard mathematical functions and notations and explores the relationships among them. It also illustrates the use of the asymptotic notations.
A function
For any real number x, we denote the greatest integer less than or equal to x by
For any integer n,
and for any integer n and integers a
and
The floor and ceiling functions are monotonically increasing.
Given a positive integer d, a polynomial in n of degree d is a function p(n) of the form
where the constants a0, a1, . . ., ad are the coefficients of the polynomial and ad
For all real a
For all n and a
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
Thus, any positive exponential function grows faster than any polynomial.
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|
When x
(In this equation, the asymptotic notation is used to describe the limiting behavior as x
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). For n > 0 and b > 1, the function logb n is strictly increasing.
For all real a > 0, b > 0, c > 0, and n,
Since changing the base of a logarithm from one constant to another only changes the value of the logarithm by a constant factor, 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
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) = lgO(1) n. We can relate the growth of polynomials and polylogarithms by substituting lg n for n and 2a for a in equation (2.5), yielding
From this limit, we can conclude that
for any constant a > 0. Thus, any positive polynomial function grows faster than any polylogarithmic function.
The notation n! (read "n factorial") is defined for integers n
Thus, n! = 1.2.3...n.
A weak upper bound on the factorial function is n!
where e is the base of the natural logarithm, gives us a tighter upper bound, and a lower bound as well. Using Stirling's approximation, one can prove
The following bounds also hold for all n:
We use the notation lg* n (read "log star of n") to denote the iterated logarithm, which is defined as follows. Let the function lg(i) n be defined recursively for nonnegative integers i as
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
The iterated logarithm is a very slowly growing function:
Since the number of atoms in the observable universe is estimated to be about 1080, which is much less than 265536, we rarely encounter a value of n such that lg* n > 5.
The Fibonacci numbers are defined by the following recurrence:
Thus, each Fibonacci number is the sum of the two previous ones, yielding the sequence
Fibonacci numbers are related to the golden ratio
Specifically, we have
which can be proved by induction (Exercise 2.2-7). Since
2.2-1
Show that if f(n) and g(n) are monotonically increasing functions, then so are the functions f(n) + g(n) and f(g(n)), and if f(n) and g(n) are in addition nonnegative, then f(n) . g(n)is monotonically increasing.
2.2-2
Use the definition of O-notation to show that T(n) = no(1) if and only if there exists a constant k > 0 such that T(n) = O(nk).
2.2-3
Prove equation (2.9).
2.2-4
Prove that lg(n!) =
2.2-5
Is the function [lg n]! polynomially bounded? Is the function [lg lg n]! polynomially bounded?
2.2-6 *
Which is asymptotically larger: lg(lg* n) or lg*(lg n)?
2.2-7
Prove by induction that the ith Fibonacci number satisfies the equality
2.2-8
Prove that for i
2-1 Asymptotic behavior of polynomials
Let
where ad > 0, be a degree-d polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.
a. If k
b. If k
c. If k = d, then p(n) =
d. If k > d, then p(n) = o(nk).
e. If k < d, then p(n) =
2-2 Relative asymptotic growths
Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o,
2-3 Ordering by asymptotic growth rates
a. Rank the following functions by order of growth; that is, find an arrangement g1, g2, . . . ,g30 of the functions satisfying g1 =
b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n)is neither O(gi(n)) nor
2-4 Asymptotic notation properties
Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.
a. f(n) = O(g(n)) implies g(n) = O(f(n)).
b. f(n) + g(n) =
c. f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) > 0 and f(n)
d. f(n) = O(g(n)) implies 2f(n) = O(2g(n)).
e. f(n) = O ((f(n))2).
f. f(n) = O(g(n)) implies g(n) =
g. f(n) =
h. f(n) + o(f(n)) =
2-5 Variations on O and
Some authors define
a. Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or f(n) =
b. Describe the potential advantages and disadvantages of using
Some authors also define O in a slightly different manner; let's use O' for the alternative definition. We say that f(n) = O'(g(n)) if and only if
c. What happens to each direction of the "if and only if" in Theorem 2.1 under this new definition?
Some authors define
0
d. Define
2-6 Iterated functions
The iteration operator "*" used in the 1g* function can be applied to monotonically increasing functions over the reals. For a function â satisfying f(n) < n, we define the function f(i) recursively for nonnegative integers i by
For a given constant c
which need not be well-defined in all cases. In other words, the quantity
For each of the following functions f (n) and constants c, give as tight a bound as possible on
Knuth [121] traces the origin of the O-notation to a number-theory text by P. Bachmann in 1892. The o-notation was invented by E. Landau in 1909 for his discussion of the distribution of prime numbers. The
Not all authors define the asymptotic notations in the same way, although the various definitions agree in most common situations. Some of the alternative definitions encompass functions that are not asymptotically nonnegative, as long as their absolute values are appropriately bounded.
Other properties of elementary mathematical functions can be found in any good mathematical reference, such as Abramowitz and Stegun [1] or Beyer [27], or in a calculus book, such as Apostol [12] or Thomas and Finney [192]. Knuth [121] contains a wealth of material on discrete mathematics as used in computer science.
-notation(n2). Let us define what this notation means. For a given function g(n), we denote by (g(n)) the set of functions(g(n)) = {â(n) : there exist positive constants c1, c2, and n0 such that
c1g(n) â(n) c2g(n) for all n 
n0}.(g(n)) if there exist positive constants c1 and c2 such that it can be "sandwiched" between c1g(n) and +c2g(n), for sufficiently large n. Although (g(n)) is a set, we write "â(n) = (g(n))" to indicate that â(n) is a member of (g(n)), or "â(n) 
(g(n))." This abuse of equality to denote set membership may at first appear confusing, but we shall see later in this section that it has advantages.(g(n)). For all values of n to the right of n0, the value of â(n) lies at or above c1g(n) and at or below c2g(n). In other words, for all n n0, the function â(n) is equal to g(n) to within a constant factor. We say that g(n) is an asymptotically tight bound for â(n).(g(n)) requires that every member of (g(n)) be asymptotically nonnegative, that is, that â(n) be nonnegative whenever n is sufficiently large. Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set (g(n)) is empty. We shall therefore assume that every function used within -notation is asymptotically non-negative. This assumption holds for the other asymptotic notations defined in this chapter as well.-notation that amounted to throwing away lower-order terms and ignoring the leading coefficient of the highest-order term. Let us briefly justify this intuition by using the formal definition to show that 1/2n2 - 3n = (n2). To do so, we must determine positive constants c1, c2, and n0 such that
n0. Dividing by n2 yields
Figure 2.1 Graphic examples of the
, O, and 
notations. In each part, the value of n0 shown is the minimum possible value; any greater value would also work. (a) -notation bounds a function to within constant factors. We write 
(n) = (g(n)) if there exist positive constants n0, c1, and c2 such that to the right of n0, the value of â(n) always lies between c1g(n) and c2g(n) inclusive. (b) O-notation gives an upper bound for a function to within a constant factor. We write â(n) = O(g(n)) if there are positive constants n0 and c such that to the right of n0, the value of â(n) always lies on or below cg(n). (c) -notation gives a lower bound for a function to within a constant factor. We write â(n) = (g(n)) if there are positive constants n0 and c such that to the right of n0, the value of â(n) always lies on or above cg(n). 1 by choosing c2 1/2. Likewise, the left-hand inequality can be made to hold for any value of n 7 by choosing c1 1/14. Thus, by choosing c1 = 1/14, c2 = 1/2, and n0 = 7, we can verify that 
. Certainly, other choices for the constants exist, but the important thing is that some choice exists. Note that these constants depend on the function 
a different function belonging to (n2) would usually require different constants.
(n2). Suppose for the purpose of contradiction that c2 and n0 exist such that 6n3 c2n2 for all n n0. But then n c2/6, which cannot possibly hold for arbitrarily large n, since c2 is constant.-notation to be satisfied. The coefficient of the highest-order term can likewise be ignored, since it only changes c1 and c2 by a constant factor equal to the coefficient.(n2). Formally, to show the same thing, we take the constants c1 = a/4, c2 = 7a/4, and n0 = 2 . max 
. The reader may verify that 0 c1n2 an2 + bn + c c2n2 for all n n0. In general, for any polynomial p(n) = 
where the ai are constants and ad > 0, we have p(n) = (nd) (see Problem 2-1).(n0), or (1). This latter notation is a minor abuse, however, because it is not clear what variable is tending to infinity.1 We shall often use the notation (1) to mean either a constant or a constant function with respect to some variable.
-calculus, the parameters to a function are clearly specified: the function n2 could be written as n.n2, or even r.r2. Adopting a more rigorous notation, however, would complicate algebraic manipulations, and so we choose to tolerate the abuse.O-notation
-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n)) the set of functions â(n) cg(n) for all n n0}.(g(n)) implies â(n) = O(g(n)), since -notation is a stronger notion than O-notation. Written set-theoretically, we have (g(n)) 
O(g(n)). Thus, our proof that any quadratic function an2 + bn + c, where a > 0, is in (n2) also shows that any quadratic function is in O(n2). What may be more surprising is that any linear function an + b is in O(n2), which is easily verified by taking c = a + |b| and n0 = 1.-notation. In this book, however, when we write â(n) = O(g(n)), we are merely claiming that some constant multiple of g(n) is an asymptotic upper bound on â(n), with no claim about how tight an upper bound it is. Distinguishing asymptotic upper bounds from asymptotically tight bounds has now become standard in the algorithms literature.(n2) bound on the worst-case running time of insertion sort, however, does not imply a (n2) bound on the running time of insertion sort on every input. For example, we saw in Chapter 1 that when the input is already sorted, insertion sort runs in (n) time.-notation-notation provides an asymptotic lower bound. For a given function g(n), we denote by (g(n)) the set of functions(g(n)) = {f(n): there exist positive constants c and n0 such that cg(n) f (n) for all n n0} .-notation is shown in Figure 2.1(c). For all values n to the right of n0, the value of f(n) is on or above g(n).(g(n)) if and only if f(n) = O(g(n)) and f(n) = (g(n)). (n2) for any constants a, b, and c, where a > 0, immediately implies that an2 + bn + c = (n2) and an2 + bn + c = O(n2). In practice, rather than using Theorem 2.1 to obtain asymptotic upper and lower bounds from asymptotically tight bounds, as we did for this example, we usually use it to prove asymptotically tight bounds from asymptotic upper and lower bounds.-notation describes a lower bound, when we use it to bound the best-case running time of an algorithm, by implication we also bound the running time of the algorithm on arbitrary inputs as well. For example, the best-case running time of insertion sort is (n), which implies that the running time of insertion sort is (n).(n) and O(n2), since it falls anywhere between a linear function of n and a quadratic function of n. Moreover, these bounds are asymptotically as tight as possible: for instance, the running time of insertion sort is not (n2), since insertion sort runs in (n) time when the input is already sorted. It is not contradictory, however, to say that the worst-case running time of insertion sort is (n2), since there exists an input that causes the algorithm to take (n2) time. When we say that the running time (no modifier) of an algorithm is (g(n)), we mean that no matter what particular input of size n is chosen for each value of n, the running time on that set of inputs is at least a constant times g(n), for sufficiently large n.Asymptotic notation in equations
(n). How do we interpret such formulas? O(n2). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example, the formula 2n2 + 3n + 1 = 2n2 + (n) means that 2n2 + 3n + 1 = 2n2 + f(n), where (n) is some function in the set (n). In this case, (n) = 3n + 1, which indeed is in (n).T(n) = 2T(n/2) +
(n).(n).
+ O(n), which doesn't really have a clean interpretation.2n2 +
(n) = (n2).(n) (n), there is some function g(n) (n2) such that 2n2 + (n) = g(n) for all n. In other words, the right-hand side of an equation provides coarser level of detail than the left-hand side.2n2 + 3n + 1 = 2n2 +
(n)=
(n2).(n) (n) such that 2n2 + 3n + 1 = 2n2 + (n) for all n. The second equation says that for any function g(n) (n) (such as the (n) just mentioned), there is some function h(n) (n2) such that 2n2 + g(n) = h(n) for all n. Note that this interpretation implies that 2n2 + 3n + 1 = (n2), which is what the chaining of equations intuitively gives us.o-notation
(n): for any positive constant c > 0, there exists a constant f(n) < cg(n) for all n n0}. o(n2).(n) = O(g(n)), the bound 0 (n) cg(n) holds for some constant c > 0, but in (n) = o(g(n)), the bound 0 (n) < cg(n) holds for all constants c > 0. Intuitively, in the o-notation, the function f(n) becomes insignificant relative to g(n) as n approaches infinity; that is,
(2.1)
-notation-notation is to -notation as o-notation is to O-notation. We use -notation to denote a lower bound that is not asymptotically tight. One way to define it is by(n) (g(n)) if and only if g(n) o((n)). (g(n)) ("little-omega of g of n") as the set(g(n)) = {(n): for any positive constant c > 0, there exists a constant cg(n) < (n) for all n n0}.(n), but n2/2 (n2). The relation (n) = (g(n)) implies that
(n) becomes arbitrarily large relative to g(n) as n approaches infinity.Comparison of functions
(n) and g(n) are asymptotically positive.â(n) =
(g(n)) and g(n) = (h(n)) imply â(n) = (h(n)),â(n) = O(g(n)) and g(n) = O(h(n)) imply â(n) = O(h(n)),
â(n) =
(g(n)) and g(n) = (h(n)) imply â(n) = (h(n)),â(n) = o(g(n)) and g(n) = o(h(n)) imply â(n) = o(h(n)),
â(n) =
(g(n)) and g(n) = (h(n)) imply â(n) = (h(n)).â(n) =
(â(n)),â(n) = O(â(n)),
â(n) =
(â(n)),â(n) =
(g(n)) if and only if g(n) = (â(n)).(n) = O(g(n)) if and only if g(n) = (f(n)),(n) = o(g(n)) if and only if g(n) = ((n)).(n) = O(g(n)) 
a b,(n) = (g(n)) a b,(n) = (g(n)) a = b,(n) = o(g(n)) a < b,(n) = (g(n)) a > b.(n) and g(n), it may be the case that neither (n) = O(g(n)) nor (n) = (g(n)) holds. For example, the functions n and n 1+sin n cannot be compared using asymptotic notation, since the value of the exponent in n1 +sin n oscillates between 0 and 2, taking on all values in between.Exercises
-notation, prove that max((n),g(n)) = (f(n) + g(n)).(n + a)b =
(nb) .(2.2)
(g(n)) if and only if its worst-case running time is O(g(n)) and its best-case running time is (g(n)).
(g(n)) is the empty set.(n,m): there exist positive constants c, n0, and m0 (n, m) cg(n, m)n0 and m m0}.(g(n, m)) and (g(n, m)).2.2 Standard notations and common functions
Monotonicity
(n) is monotonically increasing if m n implies (m) (n). Similarly, it is monotonically decreasing if m n implies (m) (n). A function (n) is strictly increasing if m < n implies (m) < (n) and strictly decreasing if m < n implies (m) > (n).Floors and ceilings
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,x - 1 <
x x x < x +1.n/2 + n/2= n, 0 and b 0,n/a/b = n/ab(2.3)
n/a/b = n/ab .(2.4)
Polynomials
0. A polynomial is asymptotically positive if and only if ad > 0. For an asymptotically positive polynomial p(n) of degree d, we have p(n) = (nd). For any real constant a 0, the function na is monotonically increasing, and for any real constant a 0, the function na is monotonically decreasing. We say that a function (n) is polynomially bounded if (n) = n0(1), which is equivalent to saying that (n) = O(nk) for some constant k (see Exercise 2.2-2).Exponentials
0, m, and n, we have the following identities:a0 = 1,
a1 = a,
a-1 = 1/a,
(am)n = amn,
(am)n = (an)m,
aman = am+n.
1, the function an is monotonically increasing in n. When convenient, we shall assume 00 = 1.
(2.5)
nb = 0(an).
(2.6)
ex
1 + x,(2.7)
1, we have the approximation1 + x
ex l + x +x2 .(2.8)
0, the approximation of ex by 1 + x is quite good:ex = 1 + x +
(x2). 0 rather than as x 
.) We have for all x,
Logarithms
lg n = log2 n (binary logarithm),
ln n = loge n (natural logarithm),
lgk n = (lg n)k (exponentiation),
lg lg n = lg(lg n) (composition).
(2.9)
x < 1:
(2.10)
lgb n = o(na)
Factorials
0 as
nn, since each of the n terms in the factorial product is at most n. Stirling's approximation,
(2.11)
n! = o(nn),
n! =
(2n),lg(n!) =
(n lg n).
(2.12)
The iterated logarithm function
lg* 2 = 1,
lg* 4 = 2,
lg* 16 = 3,
lg* 65536 = 4,
lg*(265536) = 5.
Fibonacci numbers
F0 = 0,
F1 = 1,
Fi = Fi-1+Fi-2 for i
2.(2.13)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
and to its conjugate 
, which are given by the following formulas:
(2.14)
(2.15)
< 1, we have 
, so that the ith Fibonacci number Fi is equal to 
rounded to the nearest integer. Thus, Fibonacci numbers grow exponentially.Exercises
(n lg n) and that n! = o(nn).
where is the golden ratio and 
is its conjugate. 0, the (i + 2)nd Fibonacci number satisfies Fi+2 i.Problems
d, then p(n) = O(nk). d, then p(n) = (nk).(nk).(nk)., , or of B. Assume that k 1, > 0, and c > 1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.
(g2), g2 = (g3), ..., g29 = (g30). Partition your list into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n) = (g(n)).
(gi(n)).(min(â(n), g(n))). 1 for all sufficiently large n.(f(n)).(f(n/2)).(f (n)). in a slightly different way than we do; let's use 
(read "omega infinity") for this alternative definition. We say that 
if there exists a positive constant c such that f(n) cg(n) 0 for infinitely many integers n.
(g(n)) or both, whereas this is not true if we use in place of 
instead of to characterize the running times of programs.f(n) = O'(g(n)).
(read "soft-oh") to mean O with logarithmic factors ignored:(g(n)) = {f(n): there exist positive constants c, k, and n0 such that f(n) cg(n)1gk(n) for all n n0}.
in a similar manner. Prove the corresponding analog to Theorem 2.1.
R, we define the iterated function 
by
(n) is the number of iterated applications of the function â required to reduce its argument down to c or less.
(n).
Chapter notes
and notations were advocated by Knuth [124] to correct the popular, but technically sloppy, practice in the literature of using O-notation for both upper and lower bounds. Many people continue to use the O-notation where the -notation is more technically precise. Further discussion of the history and development of asymptotic notations can be found in Knuth[121, 124] and Brassard and Bratley [33].