Skip to main content
2 of 2
added 426 characters in body
user avatar
user avatar

The recurrences of the form

$$T(n)=T(n-1)+f(n),\\T(0)=T_0$$ are solved by

$$T(n)=T_0+\sum_{k=1}^n f(n)$$

as you can check by induction.

(Because $T(n)=T(n-1)+f(n)=T(n-2)+f(n-1)+f(n)=T(n-3)+f(n-2)+f(n-1)+f(n)=\cdots$.)


From the above formula, we can obtain the asymptotic expression in an empirical way.

As the terms $n^2$ go growing, one can assume that the average resembles $n^2$ and we try the ansatz $\dfrac{T(n)}n=an^2$.

This leads to $$an^3=a(n-1)^3+n^2=an^3+(1-3a)n^2+3an-a,$$

which simplifies most when $a=\dfrac13$: $$0\sim n-\frac13.$$

As this residual is of a lower degree, we conclude

$$T(n)\sim\frac{n^3}3=\Theta(n^3).$$

Another method is to replace the sum by an integral.

user16034