Algorithm analysis - Data Structures and Problem Solving Using Java - page 214

running time bound may be significantly less than the worst-case running time
bound, and so no improvement in the bound is possible. For many complicated
algorithms the worst-case bound is achievable by some bad input, but in prac-
tice it is usually an overestimate. Two examples are the sorting algorithms
Shellsort and quicksort (both described in Chapter 8).

However, worst-case bounds are usually easier to obtain than their average-
case counterparts. For example, a mathematical analysis of the average-case run-
ning time of Shellsort has not been obtained. Sometimes, merely defining what
average means is difficult. We use a worst-case analysis because it is expedient
and also because, in most instances, the worst-case analysis is very meaningful. In
the course of performing the analysis, we frequently can tell whether it will apply
to the average case.

Average-case anal-
ysis is almost
always much more
difficult than worst-
case analysis.

summary

In this chapter we introduced algorithm analysis and showed that algorithmic
decisions generally influence the running time of a program much more than
programming tricks do. We also showed the huge difference between the run-
ning times for quadratic and linear programs and illustrated that cubic algo-
rithms are, for the most part, unsatisfactory. We examined an algorithm that
could be viewed as the basis for our first data structure. The binary search effi-
ciently supports static operations (i.e., searching but not updating), thereby
providing a logarithmic worst-case search. Later in the text we examine
dynamic data structures that efficiently support updates (both insertion and
deletion).
In Chapter 6 we discuss some of the data structures and algorithms
included in Java's Collections API. We also look at some applications of data
structures and discuss their efficiency.

key concepts

average-case bound Measurement of running time as an average over all the
possible inputs of size N . (203)
Big-Oh The notation used to capture the most dominant term in a function; it
is similar to less than or equal to when growth rates are being considered.
(190)
Big-Omega The notation similar to greater than or equal to when growth rates
are being considered. (201)
Big-Theta The notation similar to equal to when growth rates are being
considered. (202)