Why does the straightforward prefix-average algorithm run in $O(n^2)$?

The inner loop re-adds the whole prefix from scratch for every output element, so the work is $1 + 2 + \dots + n$ — an arithmetic progression, which is quadratic.

* Pass i rebuilds the whole sum from scratch, so the work grows into a triangle. *

Algorithm prefixAverages1(X, n)
  A ← new array of n integers
  for i ← 0 to n − 1 do
    s ← X[0]
    for j ← 1 to i do          ← runs i times
      s ← s + X[j]
    A[i] ← s / (i + 1)
  return A

The outer loop runs $n$ times; on pass $i$ the inner loop runs $i$ times. Total inner-loop work:

$$\sum_{i=1}^{n} i = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$$

That closed form (Gauss's summation formula) is quadratic in $n$, and by dropping constants and the lower-order term it is $O(n^2)$.

The general lesson, which is the reason this example exists: whenever a loop's inner work grows with the outer counter, you get a sum $1 + 2 + \dots + n$ rather than $n$ constant-cost passes, and the result is quadratic. This triangular pattern is the signature of nested loops, and recognising it saves you from re-deriving the sum each time.

Tip: the wasted work is visible if you look — pass $i$ recomputes the sum that pass $i-1$ already had. Carrying that running sum forward instead of rebuilding it makes the same problem $O(n)$.

Go deeper:

• Prefix sum — the linear-time version that carries the total forward, and its parallel variants.