Problem 02

Problem 02

An algorithm consists of two steps: a slow part which takes 99% of the computation time, and a fast part which takes 1% of the computation time. After someone improved the slow part (and didn't touch the fast part), the slow part takes only 98% of the total execution time. Before the improvement, the algorithm took 600 seconds to execute. How many seconds does it take after this improvement?

Solution

The fast part is unchanged, so it takes 1% of 600 seconds, which is 6 seconds. After the improvement, these 6 seconds are now 2% of the total, which means the total is now 300 seconds.

Remarks

Intuitively, students don't seem to think it's a big improvement. Their answer are all around 594 seconds. And this is a problematic misconception, especially for a computer science major. While not directly related to any theory of discrete mathematics, it is an important lesson in evaluating improvements to their work.