search
Log In
0 votes
244 views
What is the solution of recurrence relation

$T\left ( n \right )=T\left ( n-1 \right )+n$
in Algorithms 244 views

3 Answers

1 vote
 
Best answer
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)$.

0 votes

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

0 votes
1 answer
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)$
asked Jan 20, 2019 in Algorithms VikramRB 324 views
0 votes
1 answer
2
282 views
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 282 views
0 votes
1 answer
3
225 views
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked Nov 18, 2018 in Algorithms LavTheRawkstar 225 views
4 votes
3 answers
4
...