Mathematics for Computer Science

Chapter 13 Sums and Asymptotics514

0 1 2 3    n� 2 n� 1 n



^

f.n/

f.x/

f.n�1/

f.3/

f.2/

f.1/

Figure 13.2 The shaded area under the curve off.x/from 1 ton(shown in bold)
isID

Rn

1 f.x/dx.

Comparing the shaded regions in Figures 13.1 and 13.2 shows thatSis at least
Iplus the area of the leftmost rectangle. Hence,

SICf.1/ (13.17)

This is the lower bound forSgiven in (13.16).
To derive the upper bound forSgiven in (13.16), we shift the curve off.x/
from 1 tonone unit to the left as shown in Figure 13.3.
Comparing the shaded regions in Figures 13.1 and 13.3 shows thatSis at most
Iplus the area of the rightmost rectangle. That is,

SICf.n/;

which is the upper bound forSgiven in (13.16).
The very similar argument for the weakly decreasing case is left to Problem 13.10.


Theorem 13.3.2 provides good bounds for most sums. At worst, the bounds will
be off by the largest term in the sum. For example, we can use Theorem 13.3.2 to
bound the sum

SD

Xn

iD 1

p

i

as follows.