Mathematics for Computer Science

Chapter 14 Sums and Asymptotics444

describes each function’s asymptotic behavior. Full proofs are not required, but
briefly explain your answers.

(a)

nClnnC.lnn/^2

(b)

n^2 C2n 3

n^2  7

(c)

Xn

iD 0

2 2iC^1

(d)

ln.n^2 Š/

(e)

Xn

kD 1

k



1

1

2 k



Problem 14.18. (a)Either prove or disprove each of the following statements.

nŠDO..nC1/Š/

.nC1/ŠDO.nŠ/

nŠD‚..nC1/Š/

nŠDo..nC1/Š/

.nC1/ŠDo.nŠ/

(b)Show that

n

3

nCe

Do.nŠ/.

Problem 14.19.
Prove that

Pn

kD 1 k

(^6) D‚.n (^7) /.