GATE1987-10a

Question

Solve the recurrence equations:

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

Answer 1

$T(n) = T(n-1)+n$
           $=T(n-2)+(n-1)+n$
           $=T(n-3)+(n-2)+(n-1)+n$
           .
           .
           .
           $=T(n-k)+\left[(n-k+1)+ (n-k+2)+\ldots+(n-1) + n\right]$   

Recurrence stops at,

$n-k=1$
$k=n-1$

$\therefore T(n) = T(1)+\left[2+3+\ldots+n\right]
\\= 1+ 2+3+\ldots + n
\\= \frac{n(n+1)}{2}$

PS: Unless explicitly asked for asymptotic bound, we should always try to get the exact answer.

Comments

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

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

          =T(n-3)+n-2+n-1+n

            .

            .

            .

             .

T(n) = 1+2+3+4+5+6+7..........+(n-1)+n

        = n(n+1)/2

---

The best answer here is wrong answer. They haven't asked the complexity of recurrence relation. They asked solution of the given recurrence relation. So the correct answer should be n(n+1)/2

@arjun please look into this and modify the best answer to the answer given by @vicky rix

---

Asymptotic bound is not just for "complexity". But here one should give the exact answer.Had there been choice with asymptotic bound, then that would have sufficed.

---

Yes.

---

The question is tagged as' Algorithms'. I think it should be combinatorics.

Answer 2

by using master theorm

Answer 3

Here they have asked solution in terms of n and not in terms of “big-oh”

Comments

@vicky rix bro, how did you add image to the answer. I tried doing that for other questions with no success

Answer 4

I think iteration method works here pretty well(Backwards substitution)

T(1) = 1
T(2) = 2 +T(1)  = 2 + 1
T(3) = 3 + T(2)  = 3 + 2 + 1
wow a pattern right
I claim
T(n) = n + n-1 + ... + 4 + 3  +2 + 1 = n(n+1)/2