Java Reference
In-Depth Information
14
Analysis Techniques
Often it is easy to invent an equation to model the behavior of an algorithm or
data structure. Often it is easy to derive a closed-form solution for the equation
should it contain a recurrence or summation. But sometimes analysis proves more
difficult. It may take a clever insight to derive the right model, such as the snow-
plow argument for analyzing the average run length resulting from Replacement
Selection (Section 8.5.2). In this example, once the snowplow argument is under-
stood, the resulting equations follow naturally. Sometimes, developing the model
is straightforward but analyzing the resulting equations is not. An example is the
average-case analysis for Quicksort. The equation given in Section 7.5 simply enu-
merates all possible cases for the pivot position, summing corresponding costs for
the recursive calls to Quicksort. However, deriving a closed-form solution for the
resulting recurrence relation is not as easy.
Many analyses of iterative algorithms use a summation to model the cost of a
loop. Techniques for finding closed-form solutions to summations are presented in
Section 14.1. The cost for many algorithms based on recursion are best modeled
by recurrence relations. A discussion of techniques for solving recurrences is pro-
vided in Section 14.2. These sections build on the introduction to summations and
recurrences provided in Section 2.4, so the reader should already be familiar with
that material.
Section 14.3 provides an introduction to the topic of amortized analysis. Am-
ortized analysis deals with the cost of a series of operations. Perhaps a single
operation in the series has high cost, but as a result the cost of the remaining oper-
ations is limited. Amortized analysis has been used successfully to analyze several
of the algorithms presented in previous sections, including the cost of a series of
UNION/FIND operations (Section 6.2), the cost of partition in Quicksort (Sec-
tion 7.5), the cost of a series of splay tree operations (Section 13.2), and the cost of
a series of operations on self-organizing lists (Section 9.2). Section 14.3 discusses
the topic in more detail.
461
