used. There’s a major problem with that: there could be an awful lot of
schedules, especially if there are a lot of tasks.
How Hard Is Hard?
The difficulty of doing something obviously depends upon how many
things need to be done. Finding the best schedule to perform four tasks
is a slam dunk, but finding the best schedule to perform a hundred tasks
is generally a Herculean undertaking. Working with a hundred compo-
nents is obviously more time consuming than working with four compo-
nents. Let’s look at three different types of jobs.
The first job is something we all do; paying bills by mail. Generally,
you have to open the bill, write a check, and put the check in an enve-
lope. Roughly speaking, it takes as much time to do this for the electric
bill as it does for a credit card bill, and so it takes four times as long to
pay four bills as it does to pay one. Paying bills by mail is linear in the
number of components.
The second job is something that happens to all of us: you’ve put index
cards in some sort of order, either in a card box or on a Rolodex, and you
drop it. You’ve got to put the cards back in order. It turns out that this is
relatively more time consuming than paying bills, for an obvious reason:
as you continue to sort the cards, it takes longer and longer to find the
correct place for each additional card.
Finally, there is the scheduling problem. This is even more brutal than
sorting the cards for an important reason: all the components must fit to-
gether correctly, and you only know whether they fit together correctly
when you’ve finished fitting them together. When you sort the cards, you
can hold the last card in your hand and realize that you’ll be finished when
you’ve put that card in the correct spot. Such an assessment is not possible
with scheduling. As Yogi Berra so famously put it, it ain’t over ’til it’s
over.
Dropping the Rolodex
Suppose we have just dropped our Rolodex on the f loor. We now have a
bunch of file cards with names, addresses, and phone numbers on them,
and we wish to put the cards in alphabetical order. There is a very simple
way to do this: take the cards and go through them one at a time, remov-
ing each card from the unsorted pile and placing it alphabetically in the
new pile by comparing the card we just removed from the old stack with
each card in the new stack, one by one, until we find its rightful place. For
158 How Math Explains the World