Mathematics for Computer Science

13.7. Asymptotic Notation 537

Using the Integral Method of Section 13.3, we can find integers,a,b,c,d, and a
real number,e, such that

Zb

a

xedxS

Zd

c

xedx

What are appropriate values fora;:::;e?

Class Problems

Problem 13.8.
Letf WR!Rbe a continuous, weakly increasing function. Say thatf grows
slowlywhen

f.n/Do

Zn

1

f.x/dx



:

(a)Prove that the functionfa.n/WWDnagrows slowly for anya > 0.

(b)Prove that the functionendoes not grow slowly.

(c)Prove that iffgrows slowly, then

Zn

1

f.x/dx 

Xn

iD 1

f.i/:

Exam Problems

Problem 13.9.
Assumenis an integer larger than 1. Circle all the correct inequalities below.
Explanations are not required, but partial credit for wrong answers will not be
given without them.Hint:You may find the graphs in Figure 13.9 helpful.



Xn

iD 1

ln.iC1/ln 2 C

Zn

1

ln.xC1/dx



Xn

iD 1

ln.iC1/

Zn

0

ln.xC2/dx



Xn

iD 1

1

i



Zn

0

1

xC 1

dx