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 running time.

2.

But, running time depends on input. So, we decide that what really matters is running 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 running 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 running 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 running time as a function of input size for large inputs, ignoring constant factors.