Mathematics for Computer Science

Chapter 13 Sums and Asymptotics522

the leading term ofHnis ln.n/. More precisely:

Definition 13.4.2.For functionsf;gWR!R, we sayf isasymptotically equal

tog, in symbols,

f.x/g.x/

iff

lim

x!1

f.x/=g.x/D1:

Although it is tempting to writeHn ln.n/C to indicate the two leading

terms, this is not really right. According to Definition 13.4.2,Hn ln.n/Cc

wherecisany constant. The correct way to indicate that is the second-largest

term isHnln.n/.

The reason that thenotation is useful is that often we do not care about lower

order terms. For example, ifnD 100 , then we can computeH.n/to great precision

using only the two leading terms:

jHnln.n/ j

ˇ

ˇˇ

ˇ

1

200

1

120000

C

1

120
1004

ˇ

ˇˇ

ˇ<

1

200

:

We will spend a lot more time talking about asymptotic notation at the end of the

chapter. But for now, let’s get back to using sums.

13.5 Products

We’ve covered several techniques for finding closed forms for sums but no methods

for dealing with products. Fortunately, we do not need to develop an entirely new

set of tools when we encounter a product such as

nŠWWD

Yn

iD 1

i: (13.22)

That’s because we can convert any product into a sum by taking a logarithm. For

example, if

PD

Yn

iD 1

f.i/;

then

ln.P/D

Xn

iD 1

ln.f.i//: