# Made Easy Test Series:Algorithm-Recurrence Relation

244 views
What is the solution of recurrence relation

$T\left ( n \right )=T\left ( n-1 \right )+n$

1 vote

n+(n-1)+(n-2)+.....+1=$\frac{n \times (n+1)}{2}$

selected by
0
but here we donot know $T\left ( 1 \right )=1$

right??
1
Yes, it's an assumption. But unless the recurrence has a base case, it can't be solved.
1
O(n^2)
0
the solution of recurrence relation and time complexity of recurrence relation are 2 different things or the same??
0
Both are different things..
1
there is no such thing as "time complexity of recurrence relation".

Time complexity is related to algorithm means what is the running time of a particular algorithm for a given input size 'n'. To compute the running time,  we write the running time as recurrence if it has the recursive nature. The solution of that recurrence shows the time complexity of that algorithm.
1 vote
T(n) = T(n-1) + n

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

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


and so on you can substitute the value of T(n-1) and T(n-2) in T(n) to get a general idea of the pattern.

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

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

T(n) = T(n-k) + kn - k(k-1)/2    ...(1)


For base case:

n - k = 1 so we can get T(1)


=> k = n - 1
substitute in (1)

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


Which you can see is of Order $n^2 => O(n^2)$.

We can use Master Theorem for Decreasing function here.

T(n) = a* T(n-b) + n^k

Here, a=1>0 , b=1>0 and k=1

so then, O(n^k+1) i.e O(n^2)

## Related questions

1
324 views
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.