Comparing Algorithms

We want to compare algorithms to decide which we prefer.

1.

But there are many dimensions along which we might compare. So we decide that what really matters is run time.

2.

But run time depends on input. So we decide that what really matters is run time as a function of input size.

3.

But this can be hard to characterize. So we decide that what really matters is worst-case run time as a function of input size.

4.

But one algorithm might be better on small inputs and the other on large inputs. So we decide that what really matters is worst-case run time as a function of input size for large inputs.

5.

But this can still be quite hard to determine precisely. So we decide that what really matters is worst-case run time as a function of input size for large inputs, ignoring constant factors.