Update the average of a continuous sequence of numbers in constant time

Question

How can you add and subtract numbers in an average without having to iterate through the entire list?

This can be very useful in many situations. For example to continuously calculate the average of the last X values in a stream, adding two averages together, and updating a rating based on a new user vote.

Answer 1

It is indeed possible to manipulate single values in an average in constant time, O(1).

The following function adds a number to an average. average is the current average, size is the current number of values in the average, and value is the number to add to the average:

double addToAverage(double average, int size, double value)
{
    return (size * average + value) / (size + 1);
}

Likewise, the following function removes a number from the average:

double subtractFromAverage(double average, int size, double value)
{
    // if (size == 1) return 0;       // wrong but then adding a value "works"
    // if (size == 1) return NAN;     // mathematically proper
    // assert(size > 1);              // debug-mode check
    // if(size < 2) throw(...)        // always check
    return (size * average - value) / (size - 1);
}

You might consider returning 0 as the average of a set of size 0 just so adding a value back in will give that value as the average. But if you want to consider it a bug to ever reduce your set to size 0, returning NAN will propagate that to future uses, making it more visible. But see What is the arithmetic mean of an empty sequence? - you might want to just noisily report the error on the spot, or throw a C++ exception (not just raise an FP exception) if it's a bug for this to ever happen.

If you don't special case it, you'll probably get + or -Inf, from a x / 0. with non-zero x, unless the value you remove is exactly equal to the current average; then you'll get 0. / 0. => NaN.

---

You can also combine these functions to easily replace a number. This is very convenient if you are calculating the average of the last X numbers in an array/stream.

double replaceInAverage(double average, int size, double oldValue, double newValue)
{
    return (size * average - oldvalue + newValue) / size;
}

It is also possible to calculate the total average of two averages in constant time:

double addAveragesTogether(double averageA, int sizeA, double averageB, int sizeB)
{
    return (sizeA * averageA + sizeB * averageB) / (sizeA + sizeB);
}