14.7. Asymptotic Notation 435
Constant Confusion
Every constant isO.1/. For example, 17 DO.1/. This is true because if we let
f.x/D 17 andg.x/D 1 , then there exists ac > 0and anx 0 such thatjf.x/j
cg.x/. In particular, we could choosec= 17 andx 0 D 1 , sincej 17 j 17 1 for all
x 1. We can construct a false theorem that exploits this fact.
False Theorem 14.7.13.
Xn
iD 1iDO.n/Bogus proof.Definef.n/D
Pn
iD 1 iD^1 C^2 C^3 CCn. Since we have shown
that every constantiisO.1/,f.n/DO.1/CO.1/CCO.1/DO.n/.
Of course in realityPn
iD 1 iDn.nC1/=2¤O.n/.
The error stems from confusion over what is meant in the statementi DO.1/.
For anyconstanti 2 Nit is true thatiDO.1/. More precisely, iffis any constant
function, thenf DO.1/. But in this False Theorem,iis not constant—it ranges
over a set of values 0, 1,... ,nthat depends onn.
And anyway, we should not be addingO.1/’s as though they were numbers. We
never even defined whatO.g/means by itself; it should only be used in the context
“f DO.g/” to describe a relation between functionsf andg.
Lower Bound Blunder
Sometimes people incorrectly use Big Oh in the context of a lower bound. For
example, they might say, “The running time,T.n/, is at leastO.n^2 /,” when they
probably mean “n^2 DO.T.n//.”^12
Equality Blunder
The notationf D O.g/is too firmly entrenched to avoid, but the use of “=”
is really regrettable. For example, iff D O.g/, it seems quite reasonable to
writeO.g/Df. But doing so might tempt us to the following blunder: because
2nDO.n/, we can sayO.n/D2n. ButnDO.n/, so we conclude thatnD
O.n/D2n, and thereforenD2n. To avoid such nonsense, we will never write
“O.f /Dg.”
Similarly, you will often see statements like
HnDln.n/C CO1
n(^12) This would more usually be expressed as “T.n/D.n (^2) /.”