Mathematics for Computer Science

14.7. Asymptotic Notation 445

Class Problems

Problem 14.20.
Give an elementary proof (without appealing to Stirling’s formula) that log.nŠ/D
‚.nlogn/.

Problem 14.21.
Supposef;gWNC!NCandf g.

(a)Prove that2f 2g.

(b)Prove thatf^2 g^2.

(c)Give examples off andgsuch that 2 f6 2 g.

Problem 14.22.
Recall that for functionsf;gonN,f DO.g/iff

9 c 2 N 9 n 02 N 8 nn 0 c
g.n/jf.n/j: (14.34)

For each pair of functions below, determine whetherf DO.g/and whether
gDO.f /. In cases where one function is O() of the other, indicate thesmallest
nonegative integer,c, and for that smallestc, thesmallest corresponding nonega-
tive integern 0 ensuring that condition (14.34) applies.

(a)f.n/Dn^2 ;g.n/D3n.

f DO.g/ YES NO If YES,cD ,n 0 =

gDO.f / YES NO If YES,cD ,n 0 =

(b)f.n/D.3n7/=.nC4/;g.n/D 4

f DO.g/ YES NO If YES,cD ,n 0 =

gDO.f / YES NO If YES,cD ,n 0 =

(c)f.n/D 1 C.nsin.n=2//^2 ;g.n/D3n

f DO.g/ YES NO If yes,cD n 0 =

gDO.f / YES NO If yes,cD n 0 =

Problem 14.23.