When an algorithm contains an iterative control construct such as a **while** or **for** loop, its running time can be expressed as the sum of the times spent on each execution of the body of the loop. For example, we found in Section 1.2 that the *j*th iteration of insertion sort took time proportional to *j* in the worst case. By adding up the time spent on each iteration, we obtained the summation (or series)

Given a sequence *a*_{1}, *a*_{2}, . . . of numbers, the finite sum *a*_{1} + *a*_{2} + . . . +*a _{n}* can be written

Given a sequence *a*_{1}, *a*_{2}, . . . of numbers, the infinite sum *a*_{1} + *a*_{2} + can be written

If the limit does not exist, the series * diverges*; otherwise, it

For any real number *c* and any finite sequences *a*_{1}, *a*_{2}, . . . , *a _{n}* and

The linearity property is also obeyed by infinite convergent series.

The linearity property can be exploited to manipulate summations incorporating asymptotic notation. For example,

which came up when we analyzed insertion sort, is an * arithmetic series* and has the value

is a * geometric *or e

When the summation is infinite and |*x*| < 1, we have the infinite decreasing geometric series

For positive integers *n*, the *n*th **harmonic number** is

Additional formulas can be obtained by integrating or differentiating the formulas above. For example, by differentiating both sides of the infinite geometric series (3.4) and multiplying by *x*, we get

For any sequence *a*_{0}, *a*_{1}, . . . , *a _{n}*,

As an example of a telescoping sum, consider the series

Since we can rewrite each term as

The finite product *a*_{1} *a*_{2} *a _{n}* can be written

Show that by manipulating the harmonic series.

Use the linearity property of summations to prove that

There are many techniques available for bounding the summations that describe the running times of algorithms. Here are some of the most frequently used methods.

as long as (1/3 + 1/*c*) 1 or, equivalently, *c* 3/2. Thus, , as we wished to show.

In general, for a series , then

for all *k* 1. Thus, each term is bounded above by (1/3)(2/3)* ^{k}*, so that

which is an asymptotically tight bound, since .

we observe that the ratio of consecutive terms is

if *k* 3. Thus, the summation can be split into

since the second summation is a decreasing geometric series.

For the upper bound, we derive the inequality

Show that is bounded above by a constant.

Find an asymptotic upper bound on the summation

Show that the nth harmonic number is (1g n) by splitting the summation.

Give asymptotically tight bounds on the following summations. Assume that *r* 0 and *s* 0 are constants.