14.7. Asymptotic Notation 447
Problem 14.26.
(a)Define a functionf.n/such thatf D‚.n^2 /andNOT.f n^2 /.(b)Define a functiong.n/such thatgDO.n^2 /,g¤‚.n^2 /andg¤o.n^2 /.Problem 14.27. (a)Show that
.an/b=n1:wherea;bare positive constants anddenotes asymptotic equality.Hint:anD
a2log^2 n.
(b)Show that
pn
nŠD‚.n/:Problem 14.28.
(a)Define two functionsf;gthat are incomparable under big Oh:f ¤O.g/ANDg¤O.f /:(b)For each of the asymptotic relations below on the set of nonnegative real-
valued functions, indicate whether it istransitivebut not a partial order (Tr), atotal
order(Tot), astrict partial orderthat is not total (Str), aweak partial orderthat is
not total (Wk), ornoneof the above (Non).
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.