The mean misleads: why the minimum is the true measure of a function’s run time

Imagine: you’ve got a function and you’d like to know how long it takes to run, on average. So you run the function a few times, measuring how long it takes each time, then take the average of those times.

That couldn’t possibly be wrong, could it?

In this post I will make the case that taking the mean is indeed the wrong approach most of the time, and that taking the minimum will give superior results. The reasoning behind this assertion is quite straightforward, and I’m pretty sure that by the time you’ve finished reading this article, you’ll agree.

I am not claiming that taking the minimum is better than analysing and understanding your data. Only that if you aren’t going to analyse your data, don’t know anything about its distribution, and are using a single-value aggregation to represent it, then the min is a better choice than the mean most of the time.

Before I start defaming the mean, let’s talk about…

What means are good for

The below chart represents a distribution with the mean value marked.

If you had to place a bet on which number would be drawn next from this distribution, the smart money would be on the mean: 100.