Chapter 13 Sums and Asymptotics544
Problem 13.23.
Indicate which of the following holds for each pair of functions.f.n/;g.n//in
the table below. Assumek 1 , > 0, andc > 1are constants. Pick the four
table entries you consider to be the most challenging or interesting and justify your
answers to these.
f.n/ g.n/ fDO.g/ f Do.g/ gDO.f / gDo.f / f D‚.g/ fg
p^2 n^2 n=2
n nsin.n=2/
log.nŠ/ log.nn/
nk cn
logkn n
Problem 13.24.
Letf,gbe nonnegative real-valued functions such that limx!1f.x/D 1and
f g.
(a)Give an example off;gsuch thatNOT.2f 2 g/.
(b)Prove that logf logg.
(c)Use Stirling’s formula to prove that in fact
log.nŠ/nlogn
Problem 13.25.
Determine which of these choices
‚.n/; ‚.n^2 logn/; ‚.n^2 /; ‚.1/; ‚.2n/; ‚.2nlnn/; none of these
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