13.7. Asymptotic Notation 549
f DO.g/AND NOT.gDO.f //.(b)Indicate the implications among the assertions in part (a). For example,
fDo.g/IMPLIESfDO.g/:Problem 13.39.
Recall that iffandgare nonnegative real-valued functions onZC, thenf DO.g/
iff there existc;n 02 ZCsuch that
8 nn 0 :f.n/cg.n/:
For each pair of functionsf andgbelow, indicate thesmallestc 2 ZC, and
for that smallestc, thesmallest correspondingn 0 2 ZC, that would establish
f DO.g/by the definition given above. If there is no suchc, write 1.
(a)f.n/D^12 lnn^2 ;g.n/Dn. cD ,n 0 =(b)f.n/Dn;g.n/Dnlnn. cD ,n 0 =(c)f.n/D 2 n;g.n/Dn^4 lnn cD ,n 0 =(d)f.n/D 3 sin.n 1/
100C2;g.n/D0:2. cD ,n 0 =Problem 13.40.
LetGbe the set of all finiteconnectedsimple graphs, and letf;gWG!RC. We
will extend theO./notation to such graph functions as follows:
Œf DO.g/ç IFF 9 c 2 RC 9 n 02 N 8 n > n 08 n-vertexG 2 G:f.G/cg.G/:
For each of the following assertions, state whether it is true or false, andbriefly
explain your answer. You arenotexpected to offer a careful proof or detailed
counterexample.
Reminder:V.G/is the set of vertices andE.G/is the set of edges ofG.
(a)jV.G/jDO.jE.G/j/.
(b)jE.G/jDO.jV.G/j/.(c)jV.G/jDO. .G//, where .G/is the chromatic number ofG.(d) .G/DO.jV.G/j/.