Introduction to Algorithms, Third Edition

if
n
1
2
return
n
3
else
x
D
F
IB
.n
1/
4
y
D
F
IB
.n
2/
5
return
x
C
y
You would not really want to compute large Fibonacci numbers this way, be-
cause this computation does much repeated work. Figure 27.1 shows the tree of
recursive procedure instances that are created when computing
F
6
. For example,
a call to F
IB
.6/
recursively calls F
IB
.5/
and then F
IB
.4/
. But, the call to F
IB
.5/
also results in a call to F
IB
.4/
. Both instances of F
IB
.4/
return the same result
(
F
4
D
3
). Since the F
IB
procedure does not memoize, the second call to F
IB
.4/
replicates the work that the first call performs.
Let
T .n/
denote the running time of F
IB
.n/
. Since F
IB
.n/
contains two recur-
sive calls plus a constant amount of extra work, we obtain the recurrence
T .n/
D
T .n
1/
C
T .n
2/
C
‚.1/ :
This recurrence has solution
T .n/
D
‚.F
n
/
, which we can show using the substi-
tution method. For an inductive hypothesis, assume that
T .n/
aF
n
b
, where
a > 1
and
b > 0
are constants. Substituting, we obtain

---

776
Chapter 27
Multithreaded Algorithms
T .n/
.aF
n
1
b/
C
.aF
n
2
b/
C
‚.1/
D
a.F
n
1
C
F
n
2
/
2b
C
‚.1/
D
aF
n
b
.b
‚.1//
aF
n
b
if we choose
b
large enough to dominate the constant in the
‚.1/
. We can then
choose
a
large enough to satisfy the initial condition. The analytical bound
T .n/
D
‚.
n
/ ;
(27.1)
where
D
.1
C
p
5/=2
is the golden ratio, now follows from equation (3.25).
Since
F
n
grows exponentially in
n
, this procedure is a particularly slow way to
compute Fibonacci numbers. (See Problem 31-3 for much faster ways.)
Although the F
IB
procedure is a poor way to compute Fibonacci numbers, it
makes a good example for illustrating key concepts in the analysis of multithreaded
algorithms. Observe that within F
IB
.n/
, the two recursive calls in lines 3 and 4 to
F
IB
.n
1/
and F
IB
.n
2/
, respectively, are independent of each other: they could
be called in either order, and the computation performed by one in no way affects
the other. Therefore, the two recursive calls can run in parallel.
We augment our pseudocode to indicate parallelism by adding the