Mathematics for Computer Science

Chapter 13 Sums and Asymptotics548

(b)You may assume that iff.n/ 1 andg.n/ 1 for alln, thenf g!
f

(^1) n
g
(^1) n

. Show that
pnnŠD‚.n/:

Problem 13.36.

(a)Define a functionf.n/such thatf D‚.n^2 /andNOT.f n^2 /.

f.n/D

(b)Define a functiong.n/such thatgDO.n^2 /,g¤‚.n^2 /,g¤o.n^2 /, and
nDO.g/.

g.n/D

Problem 13.37. (a)Show that

.an/b=n1:

wherea;bare positive constants anddenotes asymptotic equality.Hint:anD
a2log^2 n.

(b)Show that

pnnŠD‚.n/:

Problem 13.38.

(a)Indicate which of the following asymptotic relations below on the set of non-
negative real-valued functions are equivalence relations (E), strict partial orders (S),
weak partial orders (W), ornoneof the above (N).

f g, the “asymptotically equal” relation.

f Do.g/, the “little Oh” relation.

f DO.g/, the “big Oh” relation.

f D‚.g/, the “Theta” relation.