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

=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

27 votes

Best answer

$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.

$=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.

2

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

=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

1

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

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

6 votes