2 ANALYSIS BASICS
here are many algorithms that can solve a given problem. They will
have different characteristics that will determine how efficiently each
will operate. When we analyze an algorithm, we first have to show
that the algorithm does properly solve the problem because if it doesn’t, its effi-
ciency is not important. Next, we look at how efficiently it solves the prob-
lem. This chapter sets the groundwork for the analysis and comparison of
more complex algorithms.
Analyzing an algorithm determines the amount of “time” that algorithm
takes to execute. This is not really a number of seconds or any other clock
measurement but rather an approximation of the number of operations that an
algorithm performs. The number of operations is related to the execution
time, so we will sometimes use the word time to describe an algorithm’s com-
putational complexity. The actual number of seconds it takes an algorithm to
execute on a computer is not useful in our analysis because we are concerned
with the relative efficiency of algorithms that solve a particular problem. You
should also see that the actual execution time is not a good measure of algo-
rithm efficiency because an algorithm does not get “better” just because we
move it to a faster computer or “worse” because we move it to a slower one.
The actual number of operations done for some specific size of input data
set is not very interesting nor does it tell us very much. Instead, our analysis
will determine an equation that relates the number of operations that a partic-
ular algorithm does to the size of the input. We can then compare two algo-
rithms by comparing the rate at which their equations grow. The growth rate
is critical because there are instances where algorithm A may take fewer opera-
tions than algorithm B when the input size is small, but many more when the
input size gets large.
In a very general sense, algorithms can be classified as either repetitive or
recursive. Repetitive algorithms have loops and conditional statements as their
basis, and so their analysis will entail determining the work done in the loop
and how many times the loop executes. Recursive algorithms solve a large
problem by breaking it into pieces and then applying the algorithm to each of
the pieces. These are sometimes called divide and conquer algorithms and
provide a great deal of power in solving problems. The process of solving a
large problem by breaking it up into smaller pieces can produce an algorithm
that is small, straightforward, and simple to understand. Analyzing a recursiveT