Algorithms: Recurence Relation

Question

Can someone please help me solve this recurrence relation using back substitution method:

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

Base case is T(1)=1. Also, what is the asymptotic notation?

Explanation of steps would be greatly appreciated.

Answer 1

1. Start with $n=1$: $T(1) = T(0)$.
2. Next, try $n=2$: $T(2) = T(1) + 2 = T(0) + 2$. Let $T(0) = a$, so $T(2) = a+2$.
3. Then, try $n=3$: $T(3) = T(2) + 3(2) = a+2+6 = a+8$.
4. $n=4$: $T(4) = T(3) + 4(3) = a+2+6+12 = a+20$.
5. $n=5$: $T(5) = T(4) + 5(4) = a+2(1)+3(2)+4(3)+5(4) = a+40$.

The pattern reveals itself explicitly if you do not simplify everything in advance.

It looks like $T(k) = a + 2(1) + \ldots + k(k-1) = a + \sum_{j=1}^{k-1} j(j+1) = a + \sum_{j=1}^{k-1} j^2 + \sum_{j=1}^{k-1} j$.

Now you can use usual formulas for sum of consecutive integers and consecutive integers, squared.

Oh, looks like $a=1$.

Answer 2

HINT:

If we assume $T(n)$ to be polynomial $=a_rn^r+a_{r-1}n^{r-1}+\cdots+a_1n+a_0$ where $a_i$s are independent of $n$

$$T(n)-T(n-1)=a_r\cdot r\cdot n^{r-1}+\cdots$$

$$\implies r-1=2\implies r=3 $$

Now, compare the coefficients of different powers $(3,2,1,0)$ of $n$ to determine $a_r$s where $r=3,2,1,0$

Answer 3

The homogeneous equation $S(n)=S(n-1)$ is solved by $S(n)=A$

The particular solution to $T(n)-T(n-1)=n(n-1)$ is expressed in terms of a third degree polynomial in $n$ (difference is quadratic).

The intelligent guess is $T(n)=B(n+1)n(n-1)$ so that $T(n-1)=Bn(n-1)(n-2)$ - this gives a common factor $n(n-1)$ and substituting we see we need $B=\frac 13$ so that the general solution is $$T(n)=\frac 13 (n+1)n(n-1)+A$$

If $T(1) = 1$ we have $A=1$.

Answer 4

Using magic to solve $T(n) = T(n-1) + n(n-1)$.

Since $(n+1)n(n-1)-n(n-1)(n-2) =n(n-1)\left((n+1)-(n-2)\right) =3n(n-1) $, $(n+1)n(n-1)/3 =n(n-1)(n-2)/3 +n(n-1) $, so

$\begin{align} 0 &=T(n)- T(n-1) - n(n-1)\\ &=(T(n)-(n+1)n(n-1)/3)- (T(n-1)-n(n-1)(n-2)/3 -n(n-1)) - n(n-1)\\ &=(T(n)-(n+1)n(n-1)/3)- (T(n-1)-n(n-1)(n-2)/3)\\ \end{align} $

Therefore, $T(n)-(n+1)n(n-1)/3)$ is constant for all $n$.

Since $T(1) = 1$, $T(n)-(n+1)n(n-1)/3)=1$ for all $n$, or $T(n)=(n+1)n(n-1)/3)+1$ for all $n$.