416
Relations, Functions, and Matrices
done, it is easier and often just as useful to settle for order-of-magnitude information. Sequential search is Θ(n) and binary search is Θ(log n) in the worst case.
Thus binary search is an order-of-magnitude improvement over sequential search.
The order of magnitude of an algorithm is also known as its computational complexity because it reflects the amount of work inherent in the algorithm. Table 5.3
gives a summary of the worst-case order of magnitude for algorithms discussed in
the text and exercises of Section 3.3.
table 5.3
algorithm
operation
Worst-case order of magnitude
SequentialSearch on list size n
comparisons
Θ(n)
BinarySearch on sorted list size n
comparisons
Θ(log n)
Pattern matching of pattern of length m
in text of length n
comparisons
Θ(mn)
Evaluation of a polynomial of degree n
multiplications and additions
Θ(n)
BubbleSort of list size n
comparisons
Θ(n
2
)
SelectionSort of list size n
comparisons
Θ(n
2
)
MergeSort of list size n
comparisons
Θ(n log n)
QuickSort of list size n
comparisons
Θ(n
2
)
To appreciate the effect of order of magnitude in evaluating algorithms,
suppose we have two algorithms A and A′ to do the same job but they differ
in order of magnitude—say, A is Θ(n) and A′ is Θ(n
2
). Even if each step in a
computation takes only 0.0001 second, this difference will affect total computation
time as n grows larger. The first two rows of Table 5.4 give total computation
times for A and A′ for various values of input length. Now suppose a third algorithm A″ exists whose order of magnitude is not even given by a polynomial
function but by an exponential function, say 2
n
. The total computation times for
A″ are shown in the third row of Table 5.4.
table 5.4
total computation time
Size of Input n
algorithm
order
10
50
100
A
n
0.001 second
0.005 second
0.01 second
A′
n
2
0.01 second
0.25 second
1 second
A″
2
n
0.1024 second
3570 years
4 × 10
16 centuries