Java Reference
In-Depth Information
We can expand the recurrence as many steps as we like, but the goal is
to detect some pattern that will permit us to rewrite the recurrence in terms
of a summation. In this example, we might notice that
(T(n 2) + 1) + 1 = T(n 2) + 2
and if we expand the recurrence again, we get
T(n) = T(n 2) + 2 = T(n 3) + 1 + 2 = T(n 3) + 3
which generalizes to the pattern T(n) = T(ni) + i: We might conclude
that
T(n)
= T(n (n 1)) + (n 1)
= T(1) + n 1
= n 1:
Because we have merely guessed at a pattern and not actually proved
that this is the correct closed form solution, we should use an induction
proof to complete the process (see Example 2.13).
Example2.9
A slightly more complicated recurrence is
T(n) = T(n 1) + n; T(1) = 1:
Expanding this recurrence a few steps, we get
T(n)
=
T(n 1) + n
=
T(n 2) + (n 1) + n
=
T(n 3) + (n 2) + (n 1) + n:
We should then observe that this recurrence appears to have a pattern that
leads to
T(n) = T(n (n 1)) + (n (n 2)) + + (n 1) + n
= 1 + 2 + + (n 1) + n:
This is equivalent to the summation
P
i=1
i, for which we already know the
closed-form solution.
Techniques to find closed-form solutions for recurrence relations are discussed
in Section 14.2. Prior to Chapter 14, recurrence relations are used infrequently in
this topic, and the corresponding closed-form solution and an explanation for how
it was derived will be supplied at the time of use.
