instance, suppose the top four cards on the old stack, in order, are Betty-
Al-Don-Carla. We keep track of the old stack, the new stack, and the num-
ber of comparisons that were necessary at each stage.Number of
Comparisons
Step Old Stack New Stack for This Step
1 Al-Don-Carla Betty 0
2 Don-Carla Al-Betty 1
3 Carla Al-Betty-Don 2
4 Al-Betty-Carla-Don 3If there are N cards in the new stack, the maximum number of com-
parisons that will be needed is N. For instance, at stage 3 above, the card
to be compared is Carla, and the old stack is Al-Betty-Don. Carla is be-
hind Al (first comparison), behind Betty (second comparison), in front of
Don (third comparison).
NWe can now look at the worst-case scenario for total number of compari-
sons. We’ve seen that the maximum number of comparisons needed
is the number of cards in the new stack, and since the new stack builds
up one card at a time, with N cards the maximum number of compari-
sons is 1 2 3 (N 1)N(N 1 )/2, which is a little less than(^1) ⁄ 2 N^2. Sorting N cards, even using an inefficient algorithm (better ones
are available than the one-at-a-time comparison we used in this example),
requires fewer than N^2 comparisons; such a task is said to be doable in
polynomial time (we’d say the same thing if we needed fewer than N^4 or
(^12) comparisons). Problems that can be solved in polynomial time as a
function of the number of components (cards in the above example) are
known as tractable problems. Those problems that can’t be solved in poly-
nomial time are called intractable problems.
The Traveling Salesman Problem
This may well be the problem that kicked off the subject of task complex-
ity. Suppose that a salesman has a bunch of different cities to visit, but he
starts and ends at his home base. There is a table giving the distance be-
tween each city (or, in today’s more hectic world, the travel times or pos-
sibly the costs); the goal is to devise a route that starts at home and ends
there, visits all cities once, and minimizes total travel distance (or travel
times or costs).
Murphy’s Law 159