13.7. Asymptotic Notation 531
that it is a better choice. TheO.n2:55/-operation multiplication procedure is almost
never used in practice because it only becomes more efficient than the usualO.n^3 /
procedure on matrices of impractical size.^7
13.7.3 Theta
Sometimes we want to specify that a running timeT.n/is precisely quadratic up to
constant factors (both upper boundandlower bound). We could do this by saying
thatT.n/DO.n^2 /andn^2 DO.T.n//, but rather than say both, mathematicians
have devised yet another symbol,‚, to do the job.
Definition 13.7.13.
fD‚.g/ iff fDO.g/andgDO.f /:The statementf D‚.g/can be paraphrased intuitively as “fandgare equal
to within a constant factor.”
The Theta notation allows us to highlight growth rates and suppress distracting
factors and low-order terms. For example, if the running time of an algorithm is
T.n/D10n^3 20n^2 C1;then we can more simply write
T.n/D‚.n^3 /:In this case, we would say thatTis of ordern^3 or thatT.n/grows cubically, which
is often the main thing we really want to know. Another such example is
^23 x ^7 C.2:7x^113 Cx^9 86/^4
p
x 1:083xD‚.3x/:Just knowing that the running time of an algorithm is‚.n^3 /, for example, is
useful, because ifndoubles we can predict that the running time willby and large^8
increase by a factor of at most 8 for largen. In this way, Theta notation preserves in-
formation about the scalability of an algorithm or system. Scalability is, of course,
a big issue in the design of algorithms and systems.
(^7) It is even conceivable that there is anO.n (^2) /matrix multiplication procedure, but none is known.
(^8) Since‚.n (^3) /only implies that the running time,T.n/, is betweencn (^3) anddn (^3) for constants
0 < c < d, the timeT.2n/could regularly exceedT.n/by a factor as large as8d=c. The factor is
sure to be close to 8 for all largenonly ifT.n/n^3.