computation for any problem of size n can be completed in no more than T(n)
moves on some Turing machine.
After settling on a specific type of Turing machine as a computational model,
we could analyze algorithms by writing explicit programs and counting the
number of steps involved in solving the problem. But, for a variety of reasons,
this is not overly profitable. First, the number of operations performed may vary
with the small details of the program and so may depend strongly on the
programmer. Second, from a practical standpoint, we are interested in how the
algorithm performs in the real world, which may differ considerably from how it
does on a Turing machine. The best we can hope for is that the Turing machine
analysis is representative of the major aspects of the real-life performance, for
example, the asymptotic growth rate of the time complexity. Our first attempt at
understanding the resource requirements of an algorithm is therefore invariably
an order-of-magnitude analysis in which we use the O,Θ, and notation
introduced in Chapter 1. In spite of the apparent informality of this approach, we
often get very useful information.
Example 14.1
Given a set of n numbers x 1 , x 2 ,…, x n and a key number x, determine if the set
contains x.
Unless the set is organized in some way, the simplest algorithm is just a
linear search in which we compare x successively against x 1 , x 2 ,…, until either
we find a match or we get to the last element of the set. Since we may find a
match on the first comparison or on the last, we cannot predict how much work
is involved, but we know that, in the worst case, we have to make n
comparisons. We can then say that the time-complexity of this linear search is
O(n), or even better, Θ(n). In making this analysis, we made no specific
assumptions about what machine this is run on or how the algorithm is
implemented. But the implication is that if we were to double the size of the set
of numbers, the computation time would roughly be doubled. This tells us a
great deal about searching.
EXERCISES
moves on some Turing machine.
After settling on a specific type of Turing machine as a computational model,
we could analyze algorithms by writing explicit programs and counting the
number of steps involved in solving the problem. But, for a variety of reasons,
this is not overly profitable. First, the number of operations performed may vary
with the small details of the program and so may depend strongly on the
programmer. Second, from a practical standpoint, we are interested in how the
algorithm performs in the real world, which may differ considerably from how it
does on a Turing machine. The best we can hope for is that the Turing machine
analysis is representative of the major aspects of the real-life performance, for
example, the asymptotic growth rate of the time complexity. Our first attempt at
understanding the resource requirements of an algorithm is therefore invariably
an order-of-magnitude analysis in which we use the O,Θ, and notation
introduced in Chapter 1. In spite of the apparent informality of this approach, we
often get very useful information.
Example 14.1
Given a set of n numbers x 1 , x 2 ,…, x n and a key number x, determine if the set
contains x.
Unless the set is organized in some way, the simplest algorithm is just a
linear search in which we compare x successively against x 1 , x 2 ,…, until either
we find a match or we get to the last element of the set. Since we may find a
match on the first comparison or on the last, we cannot predict how much work
is involved, but we know that, in the worst case, we have to make n
comparisons. We can then say that the time-complexity of this linear search is
O(n), or even better, Θ(n). In making this analysis, we made no specific
assumptions about what machine this is run on or how the algorithm is
implemented. But the implication is that if we were to double the size of the set
of numbers, the computation time would roughly be doubled. This tells us a
great deal about searching.
EXERCISES