What is the prefix-average problem?

Given an array $X$ of $n$ numbers, compute the array $A$ where $A[i]$ is the average of the first $i+1$ elements of $X$.

* Each point of A is the average of everything up to it — the jitter of X averages away. *

$$A[i] = \frac{X[0] + X[1] + \dots + X[i]}{i+1}$$

So $A[0]$ is just $X[0]$, $A[1]$ is the average of the first two elements, and $A[n-1]$ is the average of the whole array. Each output element summarises everything up to its position — the sequence of "running averages".

It is a genuinely useful computation, not a toy: financial analysis uses prefix and moving averages to smooth a noisy price series so that a trend is visible through the daily jitter. It also happens to be a textbook-perfect example for complexity analysis, because the obvious implementation and the clever one differ by a whole growth class — which makes it the standard vehicle for showing that how you compute something matters as much as what you compute.

Go deeper:

• Moving average — cumulative average — the same running average as a streaming computation, and what it is used for.