432
ASYMPTOTICS
subtle consideration lurks in the background. Namely, we need to realize that it’s fine to write in3 + in2 + An = O(n3), but we should neueT write this equality with the sides reversed. Otherwise we could deduce ridiculous things like n = n2 from the identities n = 0 (n2) and n2 = O(n2). When we work with O-notation and any other formulas that involve imprecisely specified quantities, we are dealing with one-way equalities. The right side of an equation does not give more information than the left side, and it may give less; the right is a “crudification” of the left. From a strictly formal point of view, the notation 0( g(n)) does not stand for a single function -f(n), but for the set of all functions f(n) such that If(n)1 6 Clg(n)l f or some constant C. An ordinary formula g(n) that doesn’t involve O-notation stands for the set containing a single function f(n) = g(n). If S and T are sets of functions of n, the notation S + T stands for the set of all functions of the form f(n) + g(n), where f(n) E S and g(n) E T; other notations like S-T, ST, S/T, &, es, In S are defined similarly. Then an “equation” between such sets of functions is, strictly speaking, a set inclusion; the ‘=’ sign reall:y means ‘g’. These formal definitions put all of our 0 manipulations on firm logical ground. For example, the “equation” in3 +
O(n’) =
O(n3)
means that S1 & S2, where S-I is the set of all functions of the form in3+f1 (n) such that there exists a constant Cl with If,(n)/ 6 Clln’I, and where S2 is the set of all functions f.!(n) such that there exists a constant CJ with Ifz(n)l 6 C21n31. we can formally prove this “equation” by taking an arbitrary element of the left-hand side and showing that it belongs to the righthand side: Given in3 + fl In) such that If,(n)1 < C11n21, we must prove that there’s a constant Cl such that l$n3 + fl (n)l 6 C21n31. The constant Cl = 3 + Cl does the trick, Isince n2 6 In31 for all integers n. If ‘=’ really means ‘C’, why don’t we use ‘c’ instead of abusing the equals sign? There are four reasons. First, tradition. Number theorists started using the equals sign with Onotation and the practice stuck. It’s sufficiently well established by now that we cannot hope to get the mathematical community to change. Second, tradition. Computer people are quite used to seeing equals signs abused- for years FORTRAN and BASIC programmers have been writing assignment statements like “N = N + 1’. One more abuse isn’t much. Third, tradition. We often read ‘=’ as the word ‘is’. For instance we verbalize the formula H, = O(log n) by saying “H sub n is Big Oh of log n!’
“And to auoide the tediouse repetition of these woordes: is equal/e to: I will sette as I doe often in woorke use, a
paire of paralleles,
or Gemowe lines of one lengthe, thus:
= , bicause
noe .2. thynges, can be moare equal/e.” - R . Recorde 12461
