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

David Gilbertson
Better Programming
Published in
16 min readMay 24, 2023

--

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.

You can think of this distribution as representing some central value (100) combined with random noise. Sometimes the noise is positive, sometimes negative, but it averages out to zero, giving a symmetric distribution.

Lots of distributions are symmetric, so the mean is a good choice as a representative value a lot of the time.

But some distributions are not symmetric, such as the run times of functions, and in these cases, the smart money is not on the mean.

Let’s look at this asymmetry in a bit more detail...

Intuition from a continuously running function

I’d like to offer a slightly odd way of looking at things, before moving on to show that this gives a good feel for what’s happening whenever we try to quantify a function’s run time.

--

--