Solve by recurrence tree: $T(n)=T(n-1)+n$

4.8k Views Asked by At

How is the recurrence tree for this relation?

The complexity of this relation is $n^2$ but can anyone explain how is it so?

1

There are 1 best solutions below

1
On

$$T(n)-T(n-1)=n$$

so,

$$T(1)-T(0)=1\\ T(2)-T(1)=2\\ T(3)-T(2)=3\\ ...\\ T(n)-T(n-1)=n$$

If we sum every equation we get:

$$T(n)-T(0)=1+2+3+...+n=\frac{n(n+1)}{2}\\ T(n)=T(0)+\frac{n^2+n}{2}$$