Mathematics for Computer Science

Chapter 14 Sums and Asymptotics422

Both cases give the same spread, albeit by different approaches. For example, see
Figure 14.9.
That was easy enough. What aboutS 3?

S 3 Dmax



1

1

6

;

3

4

C

1

6



Dmax



5

6

;

11

12



D

11

12

:

As we can see, the method provided by Case 2 is the best. Let’s checknD 4.

S 4 Dmax



1

1

8

;

11

12

C

1

8



D

25

24

: (14.21)

Wow! This is a breakthrough—for two reasons. First, equation 14.21 tells us that
by using only 4 blocks, we can make a stack so that one of the blocks is hanging
out completely over the edge of the table. The two ways to do this are shown in
Figure 14.10.
The second reason that equation 14.21 is important is that we now know that
S 4 > 1, which means that we no longer have to worry about Case 1 forn > 4since
Case 1 never achieves spread greater than 1. Moreover, even forn 4 , we have
now seen that the spread achieved by Case 1 never exceeds the spread achieved by
Case 2, and they can be equal only fornD 1 andnD 2. This means that

SnDSn 1 C

1

2n

(14.22)

for alln > 1since we have shown that the best spread can always be achieved
using Case 2.
The recurrence in equation 14.22 is much easier to solve than the one we started
with in equation 14.20. We can solve it by expanding the equation as follows:

SnDSn 1 C

1

2n

DSn 2 C

1

2.n1/

C

1

2n

DSn 3 C

1

2.n2/

C

1

2.n1/

C

1

2n