ALGORITHMS AS TECHNOLOGY

It’s pretty exciting to buy a new computer with twice, four times, or even ten times the clock rate of the old
computer. Many people think of computer hardware speed as the measure of technological advance. Having
discussed algorithms and their performance, consider whether a better algorithm on a slower computer might
be better than a slower algorithm on a faster computer.
As an example, consider a sorting task. Suppose you need to sort a million numbers (social security numbers,
for example). You have the choice of using your current computer with a merge sort program, or of buying
a new computer, which is 10 times faster, but which uses an insertion sort.
The insertion sort on the new computer will require on the order of (106)2, or a million million cycles, while
the merge sort will require on the order of 106(lg 106), or 106(20), or 20 million cycles. Even when it runs on
your old computer, the merge sort will still run four orders of magnitude faster than the insertion sort on the
new machine. If it takes 20 seconds to run the merge sort on your old machine, it will take over 27 hours to run
the insertion sort on the new machine!
Algorithm design should be considered important technology. A better algorithm can make the difference
between being able to solve the problem or not, and a better algorithm can make a much greater difference than
any near-term improvement in hardware speed.