Contents |

Order notation is used to describe the run time of an
algorithm.^{1}
in a big-picture sort of way. We often use order notation to
compare two algorithms or to compare a single algorithm to
some benchmark. For example, we might say:

f = O(n^{2})

This compares algorithm *f* to a benchmark named *n ^{2}*
and can be read as "algorithm

There are a number of letters from the Greek alphabet used to
make these comparisons. They are:
*Θ*
(theta), which means EQUIVALENT TO,
*o* (little omicron), which means LESS THAN,
*ω*
(little omega), which means GREATER THAN,
*O* (big omicron), which means LESS THAN OR EQUIVALENT TO,
and
*Ω*
(big omega), which means GREATER THAN OR EQUIVALENT TO.
The adjectives *less* and *greater* are general terms
whose meaning depends on the particular aspect
of the program being investigated.
If how fast a program runs is of interest,
then less means "takes less time to complete (runs faster)".
If how much space a program takes up when running is
of interest,
then less means "uses less space".
For all these symbols, it is generally implied
that the definitions hold only for the worst case
and for sufficiently large input.
Also, unless space or some other quantity is specified,
time is assumed.

As an example, consider two functions *f* and *g*
that perform the same task.
Consider also data sets that cause the functions
*f* and *g* to exhibit worst case behavior (i.e., take
the most time or use the most space).
Under these conditions, the
phrase
*f = ω(g)*
can be read as *f* is ALWAYS
GREATER THAN *g* in the worst case
and for sufficiently
large input.
It can also be read as *g* is
ALWAYS LESS THAN THAN *f* for
sufficiently large input in the worst case.
Suppose we are concerned with execution speed.
If indeed
*f = ω(g)*,
then we can say without a doubt that
function *f* will run slower than function *g* on the same
data set, *provided* the data set is large enough and the data set
forces both *f* and *g* to exhibit their worst case behavior.
That is, as the sizes
of these worst case data sets grow, the ratio of *g*'s running time
to *f*'s running
time will become smaller and smaller.
Eventually,
the data set sizes becomes large enough that *g* will run faster than *f* in
an absolute sense (on a worst case data set) and the ratio of running
times will be less than 1.
Moreover, this ratio will diminish towards zero as the data sets
get ever larger.

Here's another example. Let's say that by counting steps we see that
function *r* takes exactly *n ^{2}* steps in the worst case where

The common benchmarks against which programs are often compared are:

| meaning |

1 | constant |

log n | logarithmic |

n | linear |

n ^{2} | quadratic |

n ^{3} | cubic |

n log n | log-linear |

2 ^{n} | exponential |

n! | factorial |

When using order notation, we ignore constants and lower order terms.
Suppose an program *f* takes time *4n ^{2} - 3n + 105*. For an input
size

f = Θ(g)

We can see that this is true by ignoring constants and
lower order terms. The program *f* starts out as:

f = Θ(4n^{2}-3n + 105)

Removing lower order terms yields:

f = Θ(4n^{2})

Ignoring constant factors yields:

f = Θ(n^{2})

By the same token

g = Θ(5n^{2}+ 1n + 2)

g = Θ(5n^{2})

g = Θ(n^{2})

Since both *f* and *g* are *
Θ(n ^{2})*,
they are

Suppose we have two algorithms, *f* and *g*, and that:

f = o(g)

While *f* will run faster than *g* when the input size is large enough
and the input causes both *f* and *g* to exhibit worst case behavior,
it does *not*
mean that *f* runs faster than *g* in *all* cases. There
may be small worst case data sets for which *g* runs faster. There may be
rather large data sets for which *f* exhibits worst case behavior and
*g* does not, leading *g* to again have a faster running time. The function
*f* runs faster than *g* ONLY in the worst case *and* ONLY for sufficiently
large inputs.
A common mistake is to make the assumption that order notation holds
for all inputs; it does not.

Suppose instead that:

f = Θ(g)

Does this mean that *f* has exactly the same running
time as *g*?
Again, no, not really.
What
this does say is that *f* and *g* have running times within a constant
factor of each other when worst case behavior is exhibited with
sufficiently large inputs.

With the following Venn diagram, the definitions of the symbols used for order notation will become more intuitive (hopefully):

Suppose:

f = Ω(g)

Start by placing *g* in the *Θ* region.
Since *f* is *Ω*, *f* can be placed in either the
*Θ* region or the *ω* region. Thus, *f* runs
within a constant factor of *g* or slower, for sufficiently
large input that forces worst case behavior.

Contents |