Chapter 13 Sums and Asymptotics520
Here is a value0:577215664:::calledEuler’s constant, and.n/is between 0
and 1 for alln. We will not prove this formula.
We are now finally done with our analysis of the book stacking problem. Plug-
ging the value ofHninto (13.19), we find that the maximum overhang fornbooks
is very close to1=2ln.n/. Since ln.n/grows to infinity asnincreases, this means
that if we are given enough books we can get a book to hang out arbitrarily far
over the edge of the table. Of course, the number of books we need will grow as
an exponential function of the overhang; it will take 227 books just to achieve an
overhang of 3, never mind an overhang of 100.
Extending Further Past the End of the Table
The overhang we analyzed above was the furthest out thetopbook could extend
past the table. This leaves open the question of if there is some better way to build
a stable stack where some book other than the top stuck out furthest. For example,
Figure 13.8 shows a stable stack of two books where the bottom book extends
further out than the top book. Moreover, the bottom book extends 3/4 of a book
length past the end of the table, which is the same as the maximum overhang for
the top book in a two book stack.
Since the two book arrangement in Figure 13.8(a) ties the maximum overhang
stack in Figure 13.8(b), we could take the unique stable stack ofnbooks where the
top book extends furthest, and switch the top two books to look like Figure 13.8(a).
This would give a stable stack ofnbooks where the second from the top book
extends the same maximum overhang distance. So forn > 1, there are at least
two ways of building a stable stack ofnbooks which both extend the maximum
overhang distance—one way where the top book is furthest out, and another way
where the second from the top book is furthest out.
It turns out that there is no way to beat these two ways of making stable stacks.
In fact, it’s not too hard to show that these are theonlytwo ways to get a stable
stack of books that achieves maximum overhang.
But there is more to the story. All our reasoning above was about stacks in which
onebook rests on another. It turns out that by building structures in which more
than one book rests on top of another book—think of an inverted pyramid—it is
possible to get a stack ofnbooks to extend proportional to^3
p
n—much more than
lnn—book lengths without falling over. See [13],Maximum Overhang.
13.4.3 Asymptotic Equality
For cases like equation 13.21 where we understand the growth of a function likeHn
up to some (unimportant) error terms, we use a special notation,, to denote the
leading term of the function. For example, we say thatHnln.n/to indicate that