= Solution
Multiplying the <recurrence relation> by $n$ removes the average:
$$
nT(n)=\sum_{i=0}^{n-1}T(i)+n^2.
$$
For $n\geq2$, subtract the same identity at $n-1$:
$$
nT(n)-(n-1)T(n-1)=T(n-1)+n^2-(n-1)^2.
$$
Rearranging gives $T(n)=T(n-1)+2-1/n$. This also holds at $n=1$, because the original <recurrence relation> gives $T(1)=1$ and $T(0)=0$. Summing the differences therefore yields
$$
\boxed{T(n)=2n-H_n=O(n)},\qquad H_n=\sum_{j=1}^{n}\frac1j,\quad H_0=0.
$$
Here $H_n$ is a <harmonic number>. Since $H_n\leq n$, we have $n\leq T(n)\leq2n$ for $n\geq1$, also establishing $\Theta(n)$ in <big theta notation>.
Back to article page
