Mathematics for Computer Science

Chapter 14 Sums and Asymptotics442

(b)Over the firstnseconds, what fraction of the rug does the bug cross altogether?
Express your answer in terms of the Harmonic numberHn.

(c)The known universe is thought to be about 3
1010 light years in diameter.
How many universe diameters must the bug travel to get to the end of the rug?

Problems for Section 14.7

Practice Problems

Problem 14.11.
Letf.n/Dn^3. For each functiong.n/in the table below, indicate which of the
indicated asymptotic relations hold.

g.n/ f DO.g/ f Do.g/ gDO.f / gDo.f /

6 5n4n^2 C3n^3

n^3 logn

.sin.n=2/C 2 /n^3

nsin.n=2/C^2

lognŠ

e0:2n100n^3

Problem 14.12.
Circle each of the true statements below.
Explanations are not required, but partial credit for wrong answers will not be
given without them.

 n^2 n^2 Cn

 3 nDO

2 n

 nsin.n=2/C^1 Do

n^2

 nD‚



3n^3

.nC1/.n1/



Problem 14.13.
Show that
ln.n^2 Š/D‚.n^2 lnn/