Properties of Algorithm Analysis
Algorithm analysis is used to look at the "big picture"
while ignoring details.
This view is justified for most analysis,
since the "big picture" typically dominates the details
for many practical concerns.
- Use worst-case behavior rather than average-case behavior.
Although the average case behavior might be more
representative, it is often much harder to compute,
and it implies a uniformity of possible inputs that may not
be true in practice.
This assumptions places an upper bound on the resources needed
by a program.
- Focus on functional form of analysis,
while (for the most part) ignoring constants.
For all but the smallest inputs, the functional form
typically dominates the constants.
For example, 2n^2 >> 100n for all values of n > 80.
This assumption allows us to ignore details about the
particular machine or compiler in use.
- Low-order terms don't matter.
For most inputs of interest,
n^2 dominates n, regardless of the associated constants.
This assumption usually means we should focus on the nested
loops in a program, since that is where most of the program's
complexity resides.