466 pdfsam Graham, Knuth, Patashnik Concrete Mathematics

452 ASYMPTOTICS This last estimate follows because, for example, k>n (Exercise 54 discusses a more general way to esti...

0 downloads 94 Views 16KB Size
452 ASYMPTOTICS This last estimate follows because, for example,

k>n

(Exercise 54 discusses a more general way to estimate such tails.) The third sum in (9.60) is

by an argument that’s already familiar. So (9.60) proves that p% 9n

= 7 + 0 (log

n/n)3

Finally, we can feed this formula back into the recurrence, bootstrapping once more; the result is en2/b 9 n = 7 + O(logn/n3) (Exercise 23 peeks inside the remaining 0 term.) Trick 2: Trading tails. We derived (9.62) in somewhat the same way we derived the asymptotic value (9.56) of O(n): In both cases we started with a finite sum but got an asymptotic value by considering an infinite sum. We couldn’t simply get the infinite sum by introducing 0 into the summand; we had to be careful to use one approach when k was small and another when k was large. Those derivations were special cases of an important three-step asymptotic summation method we will now discuss in greater generality. Whenever we want to estimate the value of x k ok (n), we can try the following approach: 1

First break the sum into two disjoint ranges, D, and T,,. The summation over D, should be the “dominant” part, in the sense that it includes enough terms to determine the significant digits of the sum, when n is large. The summation over the other range T,, should be just the “tail” end, which contributes little to the overall total.

2

Find an asymptotic estimate ak(n) =

bk(n)

+

O(ck(n))

that is valid when k E D,. The 0 bound need not hold when k E T,.

(This important method waS pioneered by Lap/ace [195 ‘1.)