## Monday, December 23, 2002

### A Note on Running Times

Suppose you have two papers to review that give algorithmic improvements for two different problems. Here n is the input size.

Paper A: Old Running Time was 4n. New Running time is 2n.

Paper B: Old Running Time was n4. New Running time is n2.

Which paper gives the best improvement? This is not such an easy question to answer. Here are three ways to look at the question with three different results.

Analysis 1: Consider the improvement as a function of the input size: Old Running Time divided by New Running Time. Paper A is the clear winner with an improvement of 2n over the n2 improvement of Paper B.

Analysis 2: Consider the improvement as a function of the old running time. Here we have a tie; in both papers the new running time is the square root of the old running time.

Analysis 3: Suppose we are interested in the largest problem we can solve with current technology. Fix a time t and consider the largest problem we can solve in time t. In the Paper A we go from (log t)/2 to log t, a factor of 2 improvement. Paper B does much better going from t1/4 to t1/2, a quadratic improvement.