1
$\begingroup$

I've solved the recurrence relation $T(n)=T(n-1)+cn$ (where T(1)=1), getting $1+c(\frac{n(n+1)}{2}-1)$, but I can't seem to get the pre-replacement step involving $k$.

Here's what I have:

$T(n-1)+cn$

$T(T(n-2)+cn)+cn=T(n-2)+2cn$

$T(T(n-3)+cn)+2cn = T(n-3)+3cn$

$\dots$

$T(n-k)+kcn$

$k=n-1$, so the post-replacement step is $T(1)+(n-1)cn$

This is wrong, however, since $T(3)=1+5c$, whereas $T(1)+(3-1)(3)c=1+6c$

What am I doing wrong here?

$\endgroup$
4
$\begingroup$

In your calculations, the placement of the parentheses is not correct. And for example it should be $T(n-1)=T(n-2)+c(n-1)$.

One can travel from top down, or from bottom up. For this problem, I prefer bottom up. But it looks as if you are working top down, so I will do it that way. We have $$T(n)=T(n-1)+nc.$$ But $T(n-1)=T(n-2)+(n-1)c$, so $$T(n)=T(n-2)+(n-1)c+nc.$$ But $T(n-2)=T(n-3)+ (n-2)c$ and therefore $$T(n)=T(n-3)+(n-2)c+(n-1)c+nc.$$ Continue. At the end we use $T(2)=T(1)+2c=1+2c$. We conclude that $$T(n)=1+(2+3+\cdots +n)c.$$ Finally, use the standard fact that $1+2+\cdots +n=\frac{n(n+1)}{2}$, giving $2+3+\cdots +n=\frac{n^2+n-2}{2}$. That gives $$T(n)=1+\frac{n^2+n-2}{2}c.$$

One might want to note that $n^2+n-2=(n-1)(n+2)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great answer, thanks very much! $\endgroup$ – mirai Oct 20 '12 at 1:21
0
$\begingroup$

Here is your final solution

$$ T(n)= 1-c-c \left( n+1 \right) +c \left( n+1 \right) \left( \frac{1}{2}\,n+1\right) \,.$$

For how to solve it you can follow this technique or that method.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I need to see how you solved it. The approach you linked doesn't really clarify it for me. $\endgroup$ – mirai Oct 20 '12 at 0:43
0
$\begingroup$

Suppose $T(n) = T(n-1)+f(n)$. Then $T(n) = T(n-2) + f(n-1) + f(n) = T(n-3) + f(n-2)+f(n-1)+f(n) $. Continuing by induction, for $k \le n$, $T(n) = T(n-k)+\sum_{j=0}^{k-1} f(n-j)$. Letting $k = n-1$, $T(n) = T(1)+\sum_{j=0}^{n-2} f(n-j) = T(1)+\sum_{j=2}^{n} f(j) $.

If we know $T(m)$, we can get $T(n) = T(m)+\sum_{j=m+1}^{n} f(j) $.

In your case, since we know $T(1)=1$ and $f(n) = cn$, $T(n) = T(1)+\sum_{j=2}^{n} f(j) = 1 + \sum_{j=2}^{n} cn = 1 + c(\frac{n(n+1)}{2} - 1) $.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

An alternative solution:

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

Sum from $n=2$ to $n=k$ since LHS is a telescoping sum.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.