Recursion - Data Structures and Problem Solving Using Java - page 326

Proof of
Theorem 7.4
(Method 2)

(continued from previous page)

T ()
N

TN /2 ( )

------------ = ------------------ + 1

N /2

TN /2 ( ) TN /4 ( )

= + 1

------------------ ------------------

N /2 N /4

(7.8)

TN /4 ( ) TN /8 ( )

------------------ = ------------------ + 1

N /4 N /8

…

T ()
2

T ()
1

----------- = ----------- + 1

Now we add the collective in Equation 7.8. That is, we add all the terms on the left-
hand side and set the result equal to the sum of all the terms on the right-hand side.
The term appears on both sides and thus cancels. In fact, virtually all
the terms appear on both sides and cancel. This is called a telescoping sum. After
everything is added, the final result is

A telescoping
sum generates
large numbers of
canceling terms.

TN /2 ( ) / N /2 ( )

T ()
N

T ()
1

= + log N

------------ -----------

because all the other terms cancel and there are log N equations. Thus all the 1 s at
the end of these equations sum to log N . Multiplying through by N gives the final
answer, as before.

Note that, if we had not divided through by N at the start of the solution,
the sum would not have telescoped. Deciding on the division required to
ensure a telescoping sum requires some experience and makes the method a
little more difficult to apply than the first alternative. However, once you have
found the correct divisor, the second alternative tends to produce scrap work
that fits better on a standard sheet of paper, leading to fewer mathematical
errors. In contrast, the first method is more of a brute-force approach.
Note that whenever we have a divide-and-conquer algorithm that solves two
half-sized problems with linear additional work, we always have O ( N log N )
running time.