Java Reference
In-Depth Information
summation grows closer to
1
2n
;
H
n
log
e
n + +
(2.10)
where is Euler's constant and has the value 0.5772...
Most of these equalities can be proved easily by mathematical induction (see
Section 2.6.3). Unfortunately, induction does not help us derive a closed-form solu-
tion. It only confirms when a proposed closed-form solution is correct. Techniques
for deriving closed-form solutions are discussed in Section 14.1.
The running time for a recursive algorithm is most easily expressed by a recur-
sive expression because the total time for the recursive algorithm includes the time
to run the recursive call(s). A recurrence relation defines a function by means
of an expression that includes one or more (smaller) instances of itself. A classic
example is the recursive definition for the factorial function:
n! = (n 1)! n for n > 1;
1! = 0! = 1:
Another standard example of a recurrence is the Fibonacci sequence:
Fib(n) = Fib(n 1) + Fib(n 2) for n > 2;
Fib(1) = Fib(2) = 1:
From this definition, the first seven numbers of the Fibonacci sequence are
1; 1; 2; 3; 5; 8; and 13:
Notice that this definition contains two parts: the general definition for Fib(n) and
the base cases for Fib(1) and Fib(2). Likewise, the definition for factorial contains
a recursive part and base cases.
Recurrence relations are often used to model the cost of recursive functions. For
example, the number of multiplications required by function
fact
of Section 2.5
for an input of size n will be zero when n = 0 or n = 1 (the base cases), and it will
be one plus the cost of calling
fact
on a value of n1. This can be defined using
the following recurrence:
T(n) = T(n 1) + 1 for n > 1;
T(0) = T(1) = 0:
As with summations, we typically wish to replace the recurrence relation with
a closed-form solution. One approach is to expand the recurrence by replacing any
occurrences of T on the right-hand side with its definition.
Example2.8
If we expand the recurrence T(n) = T(n 1) + 1, we get
T(n)
=
T(n 1) + 1
=
(T(n 2) + 1) + 1:
