CLRS Chapter 3. Growth of Functions

chapter 2table of contentschapter 4

3.1. Asymptotic notation

Exercises

3.1-1. Let and be asymptotically nonnegative functions. Using the basic definition of -notation, prove that

Since

for all , we see that

for all .

We now choose an integer such that and for all . This implies that

for all .

It follows that .

3.1-2. Show that for any real constants and , where ,

Observe that

Let for each . We fix a positive integer such that for all . This, in particular, ipmlies that for all . Since is decreasing as increases, we see that

Now, is positive, and so it follows from the above estimates that

for all . We conclude that .

3.1-3. Explain why the statement, “The running time of algorithm is at least ,” is meaningless.

The big-O notation can only be used to give upper bounds, not lower bounds.

3.1-4. Is ? Is ?

Since

for all , we see that .

We now fix an arbitrary constant . There exists a positive integer such that for all . It then follows that

for all . Since the choice of was arbitrary, we conclude that .

3.1-5. Prove Theorem 3.1.

We recall the statement of Thereom 3.1:

For any two functions and , we have if and only if and .

Suppose that . Fix positive constants , , and such that

for all . Since

for all , we have that . Similarly,

for all , and so .

Suppose that and . The first assumption furnishes positive constants and such that

for all . The second assumption furnishes positive constants and such that

for all . It follows that

for all , whence .

3.1-6. Prove that the running time of an algorithm is if and only if its worst-case running time is and its best-case running time is .

The running time of an algorithm is bounded below by its best-case running time and bounded above by its worst-case running time. The claim now follows from Exercise 3.1-5.

3.1-7. Prove that is the empty set.

Let . For each constant , there exists a constant such that

for all . We fix an arbirary constant and observe that, for each positive constant , implies

It follows that .

Similarly, we can show that implies . It follows that the intersection is empty.

3.1-8. We can extend our notation to the case of two parameters and that can go to infinity independently at different rates. For a given function , we denote by the set of functions

Give corresponding definitions for and .

3.2. Standard notations and common functions

Exercises

3.2-1. Show that if and are monotonically increasing functions, then so are the functions and , and if and are in addition nonnegative, then is monotonically increasing.

Let . Since and , we see that

If, in addition, and are nonnegative, then

Finally, and the monotonicity of implies that

as was to be shown.

3.2-2. Prove equation (3.16).

3.2-3. Prove equation (3.19). Also prove that and .

Recall that Stirling’s approximation states that

This implies that, for each , there exists a positive integer such that implies

We fix and observe that

for all , so that

We fix positive constants , , and such that

for all . Since is a monotonically increasing function, we see that

for all .

Again, is a monotonically increasing function, there exists a positive constant such that for all . It then follows that

for all . Similarly, there exists a positive constant such that for all , and so

for all . It follows that

for all .

Now, we observe that

Whenever , we have , and so

Finally, is a monotonically increasing function, and so we can find a positive constant such that for all . It follows that

for all .

We now see that

for all . We conclude that .

We now recall that

for all .

Observe that as . Therefore, each constant admits a positive integer such that implies

It follows that .

Observe also that

whenever . Since as , we can find, for each constant , a positive integer such that implies

Therefore,

whenever . Since the choice of was arbitrary, it follows that .

3.2-4. Is the function polynomially bounded? Is the function polynomially bounded?

By Stirling’s approximation (and the continuity of ),

Since is a monotonically increasing function,

is a monotonically increasing function with limit , and so is not polynomially bounded.

Similarly,

Since as , it follows that is not polynomially bounded.

3.2-5. What is asymptotically larger: or ?

We begin by observing that

Now,

so that

It follows that grows exponentially faster than .

3.2-6. Show that the golden ratio and its conjugate both satisfy the equation .

Use the quadratic formula.

3.2-7. Prove by induction that the th Fibonacci number satisfies the equality

where is the golden ratio and its conjugate.

We first observe that

We now assume inductively that

and observe that

Since and , it follows that

as was to be shown.

3.2-8. Show that implies .

We find constants , , and such that and that

for all . This implies that

for all .

Since for all , we see that

for all . It follows that

for all and . Now, if , then . This cannot hold if , and so we conclude that

whenever .

Now, for all , and so

for all . It follows that

for all and . Since we know that whenever , we conclude that

for all .

In other words,

as was to be shown.

Problems

3-1. Asymptotic behavior of polynomials

Let

where , be a degree- polynomial in , and let be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. If , then .

b. If , then .

c. If , then .

d. If , then .

e. If , then .

Problem 3-1a

Observe that, for each ,

It follows that .

Problem 3-1b

For each fixed positive integer , we have the limit

Therefore, each positive constant has a corresponding positive integer such that implies

Taking , we see that

for all .

We now set

so that

for each and every . From this, we deduce that

for all .

Finally, we know that

whenever , and so

whenever . It follows that .

Problem 3-1c

This follows at once from 3-1a and 3-1b.

Problem 3-1d

As per 3-1b, we define, for each positive integer and every positive constant , a number to be a positive integer such that

for all .

We fix a positive constant . Observe that, for each ,

whenever . Moreover,

whenever .

Setting

we see that, for each ,

Since the choice of was arbitrary, it follows that .

Problem 3-1e

As per 3-1b, we define, for each positive integer and every positive constant , a number to be a positive integer such that

for all .

As in b, we set

so that

for all . We now fix a constant and observe that

whenever . It follows that

whenever . Since the choice of was arbitrary, we conclude that .

3-2. Relative asymptotic growths

Indicate, for each pair of expressions in the table below, whether is , , , , or of . Assume that , , and are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

 
a. yes yes no no no
b. yes yes no no no
c. no no no no no
d. no no yes yes no
e. yes no yes no yes
f. yes no yes no yes

Problem 3-2a

We define and and note that

Since , we have , and so

for all , meaning grows faster than on the interval . Since , we conclude that

for all . This, in particular, implies that

for all integers .

We now rescale for logarithm base 2, using the change-of-base formula:

for each and every .

An argument analogous to the above shows that

for all integers . Therefore,

for all and , and so it suffices to show that

for an arbitrary .

To this end, we fix a positive constant . Since as , we can find a positive constant such that for all . It follows from that

for all . Since the choice of was arbitrary, we conclude that

as was to be shown.

Problem 3-2b

Observe that and . We fix a positive constant and invoke a to find a positive integer such that

for all . Since is monotonically increasing, we conclude that

for all . The choice of was arbitrary, and so .

Problem 3-2c

We claim that there are increasing sequences of positive numbers and such that and for all . (The proof of the claim typically involves either Diophantine approximations or the Weyl equidistribution theorem.) Recall that whenever . For this reason, given any , the inequality

cannot hold for all . Similarly, the inequality

cannot hold for all . It follows that neither nor dominate each other.

Problem 3-2d

Since , we have the estimate from 3-2a.

Problem 3-2e

Observe that and . Therefore, .

Problem 3-2f

We have shown in Exercise 3.2-3 that . Since , it follows that .

3-3. Ordering by asymptotic growth rates

a. Rank the following functions by order of growth; that is, find an arrangement of the functions satisfying , , , . Partition your list into equivalence classes such that functions and are in the same class if and only if .

b. Give an example of a single nonnegative function such that for all functions in part (a), is neither nor

Problem 3-3a

Problem 3-3b

. Take a look at Problem 3.2.c to see how to prove asymptotics for functions like this one.

3-4. Asymptotic notation properties

Let and be asymptotically positive functions. Prove or disprove each of the following conjectures.

a. implies .

b.

c. implies , where and for all sufficiently large .

d. implies

e.

f. implies

g.

h. .

Problem 3-4a

, is a counterexample.

Problem 3-4b

, is a counterexample.

Problem 3-4c

Fix constants and such that

for all . Since is monotonically increasing,

for all . Now, we find such that implies . For such values of , we have

It now follows that

whence , as was to be shown.

Problem 3-4d

and is a counterexample.

Problem 3-4e

is a counterexample.

Problem 3-4f

This follows at once from the definitions of and .

Problem 3-4g

is a counterexample. To see this, we observe that

which is not asymptotically equivalent to .

Problem 3-4h

We fix and show that .

For notational convenience, we let , for an aribitrary constant , denote a positive integer such that

for all . Since

for all , we have that .

We now observe that

for all . It follows that , whence we conclude that .

3-5. Variations on and

Some authors define 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 such that for infinitely many integers .

a. Show that for any two functions and that are asymptotically nonnegative, either or or both, where as this is not true if we use in place of .

b. Describe the potential advantages and disadvantages of using instad of to characterize the running times of programs.

Some authors also define in a slightly different manner; let’s use for the alternative definition. We say that if and only if .

c. What happens to each direction of the “if and only if” in Theorem 3.1 if we substitute for but still use ?

Some authors define (read “soft-oh”) to mean with logarithmic factors ignored:

d. Define and in a similar manner. Prove the corresponding analog to Theorem 3.1.

Problem 3-5a

We assume that . This means that each and every admits a positive integer such that

Now, is an infinite set of integers such that

for all . It follows that .

Setting and , we see that .

Problem 3-5b

Introduction of renders all functions asymptotically comparable, which can be useful for making asymptotic statements about a wide class of functions without having to rule out the pathological cases (such as those involving periodic functions like ). In this manner, the utility of is analogous to that of limit superior and limit inferior, two generalizations of limit that exists for all sequences and functions.

On the other hand, the relaxed lower bound provides may not be all that useful for determining tight, or sometimes even reasonable, lower bounds for a specific function. For example, if

then our intuition suggests that cannot be a good lower bound of . Nevertheless, .

Problem 3-5c

forces to be eventually positive, and so implies . It follows from Theorem 3.1 that . Conversely, if , then Theorem 3.1 implies that and . Since , it follows that .

Problem 3-5d

We define

and

If , then we can find positive constants , , , , and such that

for all . This, in particular, implies that

for all , and so . Similarly,

for all , and so .

Conversely, we assume that and . The -estimate furnishes positive constants , , and such that

for all . The -estimate furnishes positive constants , , and such that

for all . It follows that

for all , whence .

We conclude that if and only if and .

3-6. Iterated functions.

We can apply the iteration operator used in the function to any monotonically increasing function over the reals. For a given constant , we define the iterated function by

which need not be well defined in all cases. In other words, the quantity is the number of iterated applications of reduce its argument down to or less.

For each of the following functions and constants , give as tight a bound as possible on .

 
a. 0
b. 1
c. 1
d. 2
e. 2
f. 1
g. 2
h. 2

Problem 3-6a

, and so .

Problem 3-6b

We define . For notational convenience, we write and .

For each nonnegative , there exists a unique integer such that

We can find the value of by computing for each until we reach the desired interval.

Since and are monotonically increasing, we see that

and that

It follows that .

Problem 3-6c

, and so .

Problem 3-6d

, and so .

Problem 3-6e

, and so whenever . We have .

Problem 3-6f

Observe that . Since we deal exclusively with positive integers, does converge to 1. Nevertheless, the square-root function is strictly increasing, and so implies . By induction, whenever . It follows that

Problem 3-6g

, and so whenever , where is logarithm base 3. We have for .

Problem 3-6h

whenever , and so

Additional remarks and further results

Stirling’s approximation and Euler–Maclaurin summation

In CLRS (and in many elementary probability/statistics textbooks), Stirling’s approximation is given as

A more precise asymptotic expansion can be calculated through the Euler–Mclaurin summation formula:

Euler–Maclaurin summation formula (Sedgewick/Flajolet 4.3). Let be a function defined on the interval and suppose that the derivatives exist and are absolutely integrable for , where is a fixed constant. Then

where

is a constant dependent on the function , is the th Bernoulli number, given as the th coefficient of the Taylor series

and is a remainder term satisfying the asymptotic estimate

For now, we take for granted that

By the formula, we have that

It now follows that

General form of the Euler–Maclaurin summation formula

To generalize the discrete Euler–Mclaurin summation formula, we introduce the Bernoulli polynomials

which constitute the coefficients of the Taylor series

Differentiating the Taylor series term-by-term, we see that

for each and every .

We now observe that integrating a function by parts with Bernoulli polynomial yields

Setting , we obtain the identity

We sum on to obtain

We have thus obtained the following relationship between a sum and the corresponding integral:

We can furnish a bound on by recursively integrating by parts with Bernoulli polynomials. Since , we have that

Dividing through by , we obtain a recurrence relation:

Computing recursively, we obtain:

Since and for with for odd , we see that

We now substitute and sum over to obtain

where

The remainder satisfies the estimate

Linear probing and the Ramanujan -function

An important tool in the theory of hashing (CLRS ch.11 & TAOCP vol.3, sec.6.4) is linear probing, which searches for a table with cells, of which are occupied, for a given key , inserting the key into the table whenever is not in the table and .

A famous theorem of Knuth (TAOCP vol.3, sec.6.4, Theorem K) gives an asymptotic analysis of the average number of cells linear probing examines, in terms of the Ramanujan -function

For a successful search—i.e., is inserted—the average number is

For an unsuccessful search—i.e., is not inserted—the average number is

Since

we see that

Setting , we obtain

which is a useful estimate for small values of .

At the opposite extreme, we see that , and that

which yields the following estimate (Sedgewick/Flajolet Theorem 4.8):

Knuth (TAOCP vol.1, sec.1.2.11.3) gives a refined estimate:

Ramanujan distributions

Recall from the previous section that the -distribution is

The term-by-term asymptotic estimate (Sedgewick/Flajolet, Theorem 4.4) is as follows:

Closely related to the -distribution is the -distribution

which is also asymptotically equivalent to

as . Knuth’s estimate (TAOCP vol.1, sec.1.2.11.3) is

The term-by-term asymptotic estimate of the -distribution is

as well.

Many interesting probability distributions can be represented as products of the -distribution and the -distribution. For example, each even term of the binomial distribution

can be rewritten as follows (Sedgewick/Flajolet, Theorem 4.6):

Stirling’s formula yields

whence we see that