Hello I am trying to solve this recurrence equation using the recursion tree method:
T (n) = T (n −1) + n^2 In particular, what is big-O of T (n)?
Here is what I have done so far:
I am not sure if I drew the tree correctly, and I don't know how to figure out the runtime. If someone could draw out the tree, and explain how to get the overall runtime that would be helpful.
Thanks
fyi this is repost of this post with my work added. Moderators feel free to delete the old post.
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.
