The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
132 views
What is the solution of recurrence relation

$T\left ( n \right )=T\left ( n-1 \right )+n$
in Algorithms by Veteran (116k points) | 132 views

1 Answer

+1 vote
Best answer
n+(n-1)+(n-2)+.....+1=$\frac{n \times (n+1)}{2}$
by Active (2.2k points)
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.

Related questions

+6 votes
1 answer
5
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,355 comments
90,815 users