What is Gauss's summation formula, and why does it keep appearing in complexity analysis?

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ — it is the closed form of "1 + 2 + … + n", and that sum is what nested loops and shrinking-sequence scans produce.

* Two copies of the staircase tile the box exactly — which is the formula, drawn. *

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

Why it is true, in one picture: pair the first term with the last, the second with the second-last, and so on. Each pair sums to $n+1$, and there are $n/2$ pairs — hence $n(n+1)/2$. Equivalently, the staircase of bars of heights $1, 2, \dots, n$ fills exactly half of an $n \times (n+1)$ rectangle.

Why it matters for analysis: expanded, $\frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$ — leading term $n^2$, so it is $O(n^2)$. This single fact converts a whole family of loop patterns into a growth class:

• an inner loop whose length grows with the outer counter ($1, 2, \dots, n$)
• a scan over a sequence that shrinks by one each round ($n, n-1, \dots, 1$ — the same sum backwards)

Both are $O(n^2)$, which is why selection-sort, insertion-sort and the naive prefix-average algorithm all land in the same class despite doing quite different things.

Go deeper:

• Triangular number — the pairing proof and the picture of the staircase as half a rectangle.