What is the running time of for i ← 0 to n−1 do: for j ← i to n do: s, where s costs $O(1)$? Give the exact count and the O-class.

The inner body runs $n+1, n, n-1, \dots, 2$ times, which sums to $\frac{n^2 + 3n}{2}$ — so the fragment is $O(n^2)$.

* Each outer pass runs the inner loop one time fewer: a staircase, which is quadratic. *

For a fixed i, the inner loop runs from i to n inclusive, which is $n - i + 1$ iterations. As i goes from $0$ to $n-1$:

$$\sum_{i=0}^{n-1} (n + 1 - i) = (n+1) + n + (n-1) + \dots + 2$$

This is an arithmetic series with $m = n$ terms, first term $a_1 = 2$ (counting upwards) and step $d = 1$. The general formula for such a series is

$$\sum a_i = a_1 m + \frac{m(m-1)}{2} d$$

so

$$2n + \frac{n(n-1)}{2} = \frac{4n + n^2 - n}{2} = \frac{n^2 + 3n}{2} \in O(n^2)$$

Check with $n = 5$: $6 + 5 + 4 + 3 + 2 = 20$ and $\frac{25 + 15}{2} = 20$.

The pattern to recognise: whenever the inner loop's range depends on the outer counter so that it shrinks (or grows) by one each pass, the total is a triangular sum, and a triangular sum is quadratic. The exact constants only change the lower-order terms.

Go deeper:

• Arithmetic progression — sum — the general sum formula and its derivation by pairing terms.