Chapter 14 Sums and Asymptotics446
False Claim.
2 nDO.1/: (14.35)
Explain why the claim is false. Then identify and explain the mistake in the
following bogus proof.
Bogus proof.The proof by induction onnwhere the induction hypothesis,P.n/,
is the assertion (14.35).
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 14.24. (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 path-total order.
Exam Problems
Problem 14.25. (a)Show that
.an/b=n1:wherea;bare positive constants anddenotes asymptotic equality.Hint:anD
a2log^2 n.
(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/: