# GATE1987-10a

2.4k views

Solve the recurrence equations:

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

edited

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

edited by
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
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
0
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.
0
Yes.
0
The question is tagged as' Algorithms'. I think it should be combinatorics.

by using master theorm

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

0
@vicky rix bro, how did you add image to the answer. I tried doing that for other questions with no success
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

## Related questions

1
555 views
The relative costs of assigning jobs $J_{1}, J_{2}$ and $J_{3}$ to machines $M_{1}, M_{2}$ and $M_{3}$ are given below: $\begin{array}{|c|cccc|}\hline\textbf{JOBS} && \textbf{Machines} \\ & \textbf{$M_{1}$} & \textbf{$M_{2}$} & \textbf{$ ... Using the assignment method find the assignment involving minimum cost. Is this an optimal assignment?
Let $P$ be a quicksort program to sort numbers in ascending order. Let $t_{1}$ and $t_{2}$ be the time taken by the program for the inputs $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$, respectively. Which of the following holds? $t_{1} = t_{2}$ $t_{1} > t_{2}$ $t_{1} < t_{2}$ $t_{1}=t_{2}+5 \log 5$
A voltage source e(t) $50 \sin 100$ is connected to a resistor R of 3 ohms in series with an inductor L of $0.04$ henries at time $t$ (in seconds) = 0. The expression for the current in the circuit for $1=0$ is of the form. $i(t) = Ae^{kt} + B sing (100t - \emptyset)$ Find the values of $A, K, B$ and $\emptyset$.
A Boolean function $f$ is to be realized only by $NOR$ gates. Its $K-map$ is given below: The realization is