Mathematics for Computer Science

14.7. Asymptotic Notation 443

Homework Problems

Problem 14.14. (a)Prove that logx < xfor allx > 1(requires elementary calcu-
lus).

(b)Prove that the relation,R, on functions such thatf R gifff Do.g/is a
strict partial order.

(c)Prove thatf gifff DgChfor some functionhDo.g/.

Problem 14.15.
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/ f DO.g/ f Do.g/ gDO.f / gDo.f / f D‚.g/ f g

2 n 2 n=2

p

n nsinn=2

log.nŠ/ log.nn/

nk cn

logkn n

Problem 14.16.
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 14.17.
Determine which of these choices

‚.n/; ‚.n^2 logn/; ‚.n^2 /; ‚.1/; ‚.2n/; ‚.2nlnn/; none of these