So, basically I am having a big issue with this recurrence relationship:
$$T(n) = T(n-1)+n, T(1) = 0$$
using repeated substitution I get down to:
$$i=1, T(n-1) + n$$
$$i=2, T(n-2) + 2n - 2$$
$$i=3, T(n-3) + 3n - 3$$
$$T(n) = T(n-i) + i*n - i$$
Base case: $n-i = 1, i.e. i = n - 1$
$$T(n) = T(1) + n(n-1) - (n-1)$$
$$T(n) = n^2 - 2n + 1 $$
But, wolframalpha gives me:
$$T(n) = 0.5*n^2 + 0.5*n + c$$
And with $T(1) = 0$:
$$T(n) = 0.5*n^2 + 0.5*n - 1$$
Am I doing something wrong??
Please help!!
You have applied the formula incorrectly.
If $T(n)=T(n-1)+n$, then we have
$$T(n-1)=T(n-2)+n-1$$
(Note that we have substituted $n-1$ into the original equation in place of $n$.)
Further, we have
$$T(n-2)=T(n-3)+n-2$$
So if we apply multiple-substitution, we have
$$T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=\cdots$$
Can you come up with a simpler expression which correctly conveys this value? Are you familiar with the sum over $n$ consecutive integers?
You seem to be off by 1
$$T(n) = T(n-1) + n = T(n-2) + n -1+n = T(n-2) + 2n-1$$
And you have $2n-2$. The next step gives
$$T(n) = T(n-3) + n-2 + 2n-1 = T(n-3) + 3n - 3$$
And one more gives
$$T(n) = T(n-4) + n-3 +3n-3 = T(n-4) + 4n -6$$
In geeneal the constant term will be the sum from $1$ to $k-1$ of $k$. In this case $6 = 1+2+3$. I'm sure you can find the right formula.
