Introduction: This page covers the asymptotic
notation used in your text [pages 43-52].
Figure 3.1 from your text (shown below) both illustrates and
defines the main three notations used:
Instead of saying "there exists a positive constant n0
such that for all n > n0 ...", one often says
"for all sufficiently large n ...". What happens for small
values of n doesn't matter; the only issue is what happens
for all sufficiently large values (all values after a given point,
namely n0 above). This n0
can be arbitrarily large.
The Θ-notation is used by far the most often in your text.
It's a strong statement: that
f(n) is trapped between two different constant multiples of
the same function g(n). In other words, f(n) is bounded
above and bounded below by two different multiples of g(n)
(but only when n is "sufficiently large").
The Ο-notation is used when there is a bound above, and the
(much less often used) Ω-notation is used where there is
a bound below. In fact, most people only use the Ο-notation,
and they mean by it's use roughly what the Θ-notation
says. When various other books say that a function is
Ο(n2), this of course means that it's
bounded above by a constant multiple of n2
(for all sufficiently large values of n), but
often implied is that n2 is also a lower bound,
because otherwise they would have chosen a different function to
give a tight bound (above and below). If it's only an upper bound,
this will be stated explicitly.
Example: Suppose we were to write
f(n) is O(n3 + 23*n2).
This means that there are constants c0
and n0 such that
f(n) < c0 * (n3 + 23*n2)
for all n > n0.
But if we take n1 > max(n0,23)
and c1 = 2*c0, then
f(n) < c0 * (n3 + n*n2)
= 2*c*n3 = c1*n3,
for all n > n1.
This is the definition of saying that f(n) is
O(n3). So in the big-O notation, there's
no reason to put in a term like 23*n2 if
there's also a faster growing term like n3.
Powers of n: If the time performance of an algorithm
is a sum of constants times powers of n, you only need to keep the
highest power of n. So if you have
O(14*n + 2*√n + 12*n*√n),
this is the same
as simply O(n*√n) = O(n3/2).
Revision date:2012-05-28.
(Please use ISO 8601,
the International Standard Date and Time Notation.)
