14.1 Efficiency of Computation
Let us start with a concrete example. Given a list of one thousand integers, we
want to sort them in some way, say in ascending order. Sorting is a simple
problem but also one that is very fundamental in computer science. If we now
ask the question, “How long will it take to do this task?” we see immediately
that much more information is needed before we can answer it. Clearly, the
number of items in the list plays an important role in how much time will be
taken, but there are other factors. There is the question of what computer we use
and how we write the program. Also, there are a number of sorting methods so
that selection of the algorithm is important. There are probably a few more
things you can think of that need to be looked at before you can even make a
rough guess of the time requirements. If we have any hope of producing a
general picture of sorting, most of these issues have to be ignored, and we must
concentrate on those that are fundamental.
For our discussion of computational complexity, we will make the following
simplifying assumptions.
1. The model for our study will be a Turing machine. The exact type of Turing
machine to be used will be discussed below.
2. The size of the problem will be denoted by n. For our sorting problem, n is
obviously the number of items in the list. Although the size of a problem is
not always so easily characterized, we can generally relate it in some way to
a positive integer.
3. In analyzing an algorithm, we are less interested in its performance on a
specific case than in its general behavior. We are particularly concerned with
how the algorithm behaves when the problem size increases. Because of this,
the primary question involves how fast the resource requirements grow as n
becomes large.
Our immediate goal will then be to characterize the time requirement of a
problem as a function of its size, using a Turing machine as the computer model.
First, we give some meaning to the concept of time for a Turing machine. We
think of a Turing machine as making one move per time unit, so the time taken
by a computation is the number of moves made. As stated, we want to study how
the computational requirements grow with the size of the problem. Normally, in
the set of all problems of a given size, there is some variation. Here we are
interested only in the worst case that has the highest resource requirements. By
saying that a computation has a time-complexity T(n), we mean that the
Let us start with a concrete example. Given a list of one thousand integers, we
want to sort them in some way, say in ascending order. Sorting is a simple
problem but also one that is very fundamental in computer science. If we now
ask the question, “How long will it take to do this task?” we see immediately
that much more information is needed before we can answer it. Clearly, the
number of items in the list plays an important role in how much time will be
taken, but there are other factors. There is the question of what computer we use
and how we write the program. Also, there are a number of sorting methods so
that selection of the algorithm is important. There are probably a few more
things you can think of that need to be looked at before you can even make a
rough guess of the time requirements. If we have any hope of producing a
general picture of sorting, most of these issues have to be ignored, and we must
concentrate on those that are fundamental.
For our discussion of computational complexity, we will make the following
simplifying assumptions.
1. The model for our study will be a Turing machine. The exact type of Turing
machine to be used will be discussed below.
2. The size of the problem will be denoted by n. For our sorting problem, n is
obviously the number of items in the list. Although the size of a problem is
not always so easily characterized, we can generally relate it in some way to
a positive integer.
3. In analyzing an algorithm, we are less interested in its performance on a
specific case than in its general behavior. We are particularly concerned with
how the algorithm behaves when the problem size increases. Because of this,
the primary question involves how fast the resource requirements grow as n
becomes large.
Our immediate goal will then be to characterize the time requirement of a
problem as a function of its size, using a Turing machine as the computer model.
First, we give some meaning to the concept of time for a Turing machine. We
think of a Turing machine as making one move per time unit, so the time taken
by a computation is the number of moves made. As stated, we want to study how
the computational requirements grow with the size of the problem. Normally, in
the set of all problems of a given size, there is some variation. Here we are
interested only in the worst case that has the highest resource requirements. By
saying that a computation has a time-complexity T(n), we mean that the