467 pdfsam Graham, Knuth, Patashnik Concrete Mathematics

9.4 TWO ASYMPTOTIC TRICKS 153 3 Now prove th at each of the following three sums is small: L(n) = x ok(n); tb(n) ...

0 downloads 82 Views 26KB Size
9.4 TWO ASYMPTOTIC TRICKS 153

3

Now prove th at each of the following three sums is small: L(n)

=

x

ok(n);

tb(n)

=

x

xc (n)

‘Jk(n)

;

kET,

MT, =

x

(ck(n)l.

(9W

If all three steps can be completed successfully, we have a good estimate: t

ak(n)

=

t

kED,uT,

bk(n)

+

o(L(n))

+ O(xb(n))

+ o(L(n))

.

kED,uT,

Here’s why. We can “chop off” the tail of the given sum, getting a good estimate in the range D, where a good estimate is necessary: x

ak(n) =

x @k(n)

G-D,

+ O(ck(n)))

kCD,

=

t

bk(n)

+ o&(n)).

ND,

And we can replace the tail with another one, even though the new tail might be a terrible approximation to the old, because the tails don’t really matter: x

Asymptotics is the art of knowing where to be sloppy and where to be precise.

ak(n) =

x

&T,

@k(n)

- bk(n)

+ ak(n))

MT, =

x h(n)

+

O(xb(n))

+

o&,(n)).

MT, When we evaluated the sum in (g.6o), for example, we had ak(n)

=

[06k
h(n)

=

Sk/n,

ck(n)

=

kgk/n(n-k);

the ranges of summation were

T,, = {n,n+l,...};

D, = {O,l,..., n - l } , and we found that

x,(n)

= 0, Lb(n)

= o((logn)2/n2),

xc(n) = o((logn)3/n2).

This led to (9.61). Similarly, when we estimated 0(n) in (9.55) we had ak(n) =

v(k)

[n/k]

D, = {1,2 ,..., n},

Ll+n/k]

,

bk(n)

=

dk)n2/k2

,

ck(n) =

n/k;

T,, = {n+l,n+2,...}.

We derived (9.56) by observing that E,(n) = 0, xb(n) = O(n), and L,(n) = O(nlogn).