search
Log In
20 votes
2.4k views

Solve the recurrence equations:

  • $T(n) = T(n - 1)+ n$
  • $T(1) = 1$
in Algorithms
edited by
2.4k views

4 Answers

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.

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.
14 votes

by using master theorm

6 votes

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
0 votes
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

0 votes
2 answers
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?
asked Nov 15, 2016 in Algorithms makhdoom ghaya 555 views
34 votes
6 answers
2
6k views
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$
asked Nov 9, 2016 in Algorithms makhdoom ghaya 6k views
–2 votes
0 answers
3
369 views
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$.
asked Nov 16, 2016 in Others makhdoom ghaya 369 views
16 votes
4 answers
4
1.8k views
A Boolean function $f$ is to be realized only by $NOR$ gates. Its $K-map$ is given below: The realization is
asked Nov 15, 2016 in Digital Logic makhdoom ghaya 1.8k views
...