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 4ⁿ. New Running time is 2ⁿ.

Paper B: Old Running Time was n⁴. New Running time is n².

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 2ⁿ over the n² 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 t^1/4 to t^1/2, a quadratic improvement.