Mathematics for Computer Science

Chapter 13 Sums and Asymptotics546

(a)Prove that2f 2g.

(b)Prove thatf^2 g^2.

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

Problem 13.30.
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: (13.30)

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
nonnegative integer,c, and for that smallestc, thesmallest corresponding nonneg-
ative integern 0 ensuring that condition (13.30) 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 13.31.

False Claim.
2 nDO.1/: (13.31)
Explain why the claim is false. Then identify and explain the mistake in the
following bogus proof.

Bogus proof.The proof is by induction onnwhere the induction hypothesis,P.n/,
is the assertion (13.31).