**Paper A**: Old Running
Time was 4^{n}. New Running time is 2^{n}.

**Paper B**: Old Running
Time was n^{4}. New Running time is n^{2}.

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^{n} over the
n^{2} 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.

## No comments:

## Post a Comment