Mathematics for Computer Science

Chapter 13 Sums and Asymptotics542

by each of the expressions below.

(a)2x^3 C.logx/x^2

(b)2x^2 +.logx/x^3

(c).1:1/x

(d).0:1/x

(e).x^4 Cx^2 C1/=.x^3 C1/

(f).x^4 C 5 logx/=.x^4 C1/

(g) 2 .3log^2 x

(^2) /
Problem 13.17.
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 13.18.
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/