Section 4.3 Faster Computer, or Faster Algorithm
Imagine you are faced with a problem and you have an algorithm with a running time proportional to n^2, where n represents the size of the input. However, the resulting program takes ten times longer to run than desired. If you were to replace your current computer with a new one that is ten times faster, would the n^2 algorithm become acceptable? It might seem logical that the faster computer would allow you to complete your work quickly enough, even with an algorithm that has a high growth rate, as long as the problem size remains the same. But here’s an interesting observation: when most people acquire a faster computer, they don’t necessarily run the same problem faster; they tend to tackle a larger problem instead. For example, on your old computer, you might have been content sorting 10,000 records during your lunch break. With the new, faster computer, you might aim to sort 100,000 records in the same time. Since you won’t finish your lunch any sooner, it makes sense to solve a larger problem. Additionally, due to the increased speed of the new machine, you would ideally like to sort ten times as many records.
If the algorithm’s growth rate is linear, meaning the equation describing the running time on input size n is T(n) = cn for some constant c, then sorting 100,000 records on the new machine would take the same amount of time as sorting 10,000 records on the old machine. However, if the algorithm’s growth rate exceeds cn, such as c1n^2, then it won’t be possible to solve a problem ten times the size in the same amount of time on a machine that is only ten times faster.
You have attempted of activities on this page.
