Information Technology Reference
In-Depth Information
was constant. The technique gave the appearance of being sublinear because the task
was changing.
Sometimes a formal analysis is inappropriate or only a minor consideration. For
example, an algorithm for arranging line breaks in paragraphs of text will only rarely
have to operate on a large input, so showing that a new algorithm is better than an
existing algorithm in the limit may be of less interest than showing it is better on a
typical case. More generally, although some results can be conclusively obtained by
analysis, others cannot. Analytical results often say nothing about constant factors,
for example, or behaviour in practice where CPU, cache, bus, and disk can interact in
complex ways. Such properties can only be determined by experiment. Thus, while
an asymptotic analysis tells us that a hash table should be faster than a B-tree, in
practice the B-tree may be superior for storage of records in a large database system.
That is, despite the fact that such analyses in some sense measure costs, in practical
terms they do not in general concern resources, but only concern how the resources
change with scale; and may have little bearing on performance in practice.
Moreover, an analysis is no more reliable than its assumptions. In an analysis of
a data structure, the data must be modelled in some way, perhaps with simplifica-
tions to make the analysis tractable; but there is no guarantee that the modelling is
realistic. The subjective elements of an analysis are just as significant as they are in
an experimental design, due to the need for assumptions about properties such as
machine behaviour and data distribution. Even the most fundamental assumptions,
such as that analyses concern the number of instructions to be executed, may in some
cases be inappropriate for a machine in which memory or disk references require
thousands of instruction cycles and are the dominant practical cost.
The assumptions, in most research, flow from properties of the task the algorithm
is being considered for. It may well be, for example, that a network analysis method
has an utterly intractable worst case, but it also may be that this case cannot arise in
the contexts that inspired the research, or is extraordinarily improbable. In general,
algorithms are not applied to random input, and thus there is an important distinction
between asymptotic costs in principle, asymptotic costs in plausible contexts, and
actual costs in practice—each of which can be the subject of an informative analysis.
Analytical results can be powerful indeed—with, in some cases, implications
for performance in practice on all machines for all time—but, as also discussed in
