Analysis of Algorithms
======================

Time analysis compares two (or more) algorithms with respect
to how long it takes them to run on a certain problem.

Space analysis compares two (or more) algorithms with
respect to how much memory it takes them while running on a
certain problem.

These comparisons are troublesome to perform on hardware
since machines run at different speeds and programmers code
with more/less efficiency than one another.  Not to mention
compilers optimize better/worse than one another.  Oh, and
there may be multiple processes/users taking up CPU time and
throwing the timings off.  And...  Well, let's just say it
would be easier if we could analyze algorithms 'offline' --
mathematically rather than on a particular coded version.

To do this we count the number of critical operations
performed on a problem of a certain 'size'.  (Exactly what is
a critical operation is given at this stage and will become
increasingly intuitive as your experience grows.)  This
counting gives us a function of problem size that determines
how long -- in terms of critical operations -- a particular
algorithm will take to solve the problem.

---------------------------------------------------------------------------

Mathematical analysis of algorithms helps determine to which
of several groups of algorithms the one you are analyzing
belongs.  There are three basic categorizations we use to
place one algorithm relative to a group of algorithms:  O,
W, and 0...er...rather:  Big-Oh, Big-Omega, and Big-Theta.

Big-Oh specifies that one function grows at worst as rapidly
as a reference function.

Big-Omega specifies that one function grows at least as
rapidly as a reference function.

Big-Theta specifies that two functions grow at approximately
the same rate.

Although a Big-Theta analysis would be nice, it is not
always so easy to come by.  Big-Oh is easier to work with
and is often "good enough".  (If you can get Big-Omega, too,
you can sandwich the algorithm to find Big-Theta -- it is
the intersection of Big-Oh and Big-Omega.)

---------------------------------------------------------------------------

Commonly used functions are polynomials, exponentials,
constants, logarithmic, and log-linear functions.  These
compare in terms of decreasing O() as:

    n^n
    n!
    a^n
  -------
    n^a
    n*lg(n)
    n
    lg(n)
    a

That is, a is in O(lg(n)), O(n), O(n*lg(n)), etc., lg(n) is
in O(n), O(n*lg(n)), etc., and so forth.

---------------------------------------------------------------------------

In addition to these three graphical groupings, we are also
interested in different kinds of behavior of our algorithms:
best-case, worst-case, and average-case complexities.  These
are analyses done, of course, for when our algorithm is at
its best, at its worst, and on average.

Our general tool in a mathematical analysis is this
summation:

              ---------
              \
               \
                >     p * c
               /       i   i
              /
              ---------
                ALL i

This is the sum over all inputs of the product of that
input's probability occurance and the number of steps (or
amount of space) the input requires to be processed by the
algorithm (generically called the 'count').

---------------------------------------------------------------------------

An easy way to guesstimate the Big-Oh performance of an
algorithm is to look over its loops.  Count out how many
times each loop operates.  If loops are nested, multiply
their counts.  If loops are sequenced, add their counts.
Now take the largest reference function with any coeffi-
cient removed and you have your guesstimate.  For instance,
the following algorithm:

    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            // do something interesting
        }
    }
    for (i = 1; i <= n; ++i)
    {
        // do something else interesting
    }

Would give us n^2 + n as the raw estimate and then dropping
the n we'd get n^2 as the reference function guess.

Guesstimating logarithms is a little tricky.  We'll talk
more about that in discrete math.