How is the recurrence tree for this relation?
The complexity of this relation is $n^2$ but can anyone explain how is it so?
$$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}$$
Copyright © 2021 JogjaFile Inc.
$$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}$$