13.7. Asymptotic Notation 547
base case:P.0/holds trivially.
inductive step:We may assumeP.n/, so there is a constantc > 0such that
2 nc 1. Therefore,
2 nC^1 D 2 2 n.2c/1;
which implies that 2 nC^1 DO.1/. That is,P.nC1/holds, which completes the
proof of the inductive step.
We conclude by induction that 2 n DO.1/for alln. That is, the exponential
function is bounded by a constant.
Problem 13.32. (a)Prove that the relation,R, on functions such thatf R giff
f Do.g/is a strict partial order.
(b)Describe two functionsf;gthat are incomparable under big Oh:f ¤O.g/ANDg¤O.f /:Conclude thatRis not a linear order. How about three such functions?
Exam Problems
Problem 13.33.
Give an example of a pair of strictly increasing total functions,f WNC!NCand
gWNC!NC, that satisfyf gbutnot 3 f DO. 3 g/.
Problem 13.34.
Prove that
f D‚.g/ IMPLIES lnf lng;
for all nonnegative real-valued functionsf;g.
Problem 13.35. (a)Show that
.an/b=n1:wherea;bare positive constants anddenotes asymptotic equality.Hint:anD
a2log^2 n.