13.7. Asymptotic Notation 543
Problem 13.19.
Show that
ln.n^2 Š/D‚.n^2 lnn/
Hint:Stirling’s formula for.n^2 /Š.
Problem 13.20.
The quantity
.2n/Š
2 2n.nŠ/^2(13.29)
will come up later in the course (it is the probability that in 2 2nflips of a fair coin,
exactlynwill be Heads). Show that it is asymptotically equal to
1
p
n.
Problem 13.21.
Suppose letf andgbe real-valued functions.
(a)Give an example off;gsuch thatlim supfg <lim supflim supg;and all the lim sup’s are finite.
(b)Give an example off;gsuch thatlim supfg >lim supflim supg:and all the lim sup’s are finite.
Homework Problems
Problem 13.22. (a)Prove that logx < xfor allx > 1(requires elementary calcu-
lus).
(b)Prove that the relation,R, on functions such thatf R giffgDo.f /is a
strict partial order.
(c)Prove thatf gifff DgChfor some functionhDo.g/.