Page 246 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 225

is not too large, even if it is impractical to use this algorithm for larger inputs. Furthermore,
when designing new algorithms to solve a problem, the goal is often to find a new algorithm
that is more efficient than a brute-force algorithm. One such problem of this type is described
in Example 10.
EXAMPLE 10 Construct a brute-force algorithm for finding the closest pair of points in a set of n points in
the plane and provide a worst-case big-O estimate for the number of bit operations used by the
algorithm.

Solution: Suppose that we are given as input the points (x 1 ,y 1 ), (x 2 ,y 2 ),...,(x n ,y n ). Recall

2
2
that the distance between (x i ,y i ) and (x j ,y j ) is (x j − x i ) + (y j − y i ) . A brute-force algo-
rithm can find the closest pair of these points by computing the distances between all pairs of
the n points and determining the smallest distance. (We can make one small simplification to
make the computation easier; we can compute the square of the distance between pairs of points
to find the closest pair, rather than the distance between these points. We can do this because
the square of the distance between a pair of points is smallest when the distance between these
points is smallest.)

ALGORITHM 3 Brute-Force Algorithm for Closest Pair of Points.

procedure closest-pair((x 1 ,y 1 ), (x 2 ,y 2 ),...,(x n ,y n ): pairs of real numbers)
min=∞
for i := 2 to n
for j := 1 to i − 1
2
2
if (x j − x i ) + (y j − y i ) <min then
2
min := (x j − x i ) + (y j − y i ) 2
closest pair := ((x i ,y i ), (x j ,y j ))
return closest pair

To estimate the number of operations used by the algorithm, first note that there are
n(n − 1)/2 pairs of points ((x i ,y i ), (x j ,y j )) that we loop through (as the reader should verify).
2
2
For each such pair we compute (x j − x i ) + (y j − y i ) , compare it with the current value of
min, and if it is smaller than min replace the current value of min by this new value. It follows
2
that this algorithm uses (n ) operations, in terms of arithmetic operations and comparisons.
In Chapter 8 we will devise an algorithm that determines the closest pair of points when given
n points in the plane as input that has O(n log n) worst-case complexity. The original discovery
of such an algorithm, much more efficient than the brute-force approach, was considered quite
surprising. ▲

Understanding the Complexity of Algorithms

Table 1 displays some common terminology used to describe the time complexity of algorithms.
For example, an algorithm that finds the largest of the first 100 terms of a list of n elements
by applying Algorithm 1 to the sequence of the first 100 terms, where n is an integer with
n ≥ 100, has constant complexity because it uses 99 comparisons no matter what n is (as
the reader can verify). The linear search algorithm has linear (worst-case or average-case)
complexity and the binary search algorithm has logarithmic (worst-case) complexity. Many
important algorithms have n log n,or linearithmic (worst-case) complexity, such as the merge
sort, which we will introduce in Chapter 4. (The word linearithmic is a combination of the words
linear and logarithmic.)