1 votes 1 votes What is the solution of recurrence relation $T\left ( n \right )=T\left ( n-1 \right )+n$ Algorithms algorithms time-complexity recurrence-relation + – srestha asked May 10, 2019 srestha 844 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes n+(n-1)+(n-2)+.....+1=$\frac{n \times (n+1)}{2}$ Arkaprava answered May 10, 2019 selected May 10, 2019 by srestha Arkaprava comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Hira Thakur commented Oct 11, 2019 reply Follow Share the solution of recurrence relation and time complexity of recurrence relation are 2 different things or the same?? 0 votes 0 votes Verma Ashish commented Oct 11, 2019 reply Follow Share Both are different things.. 0 votes 0 votes ankitgupta.1729 commented Oct 11, 2019 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
0 votes 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) AbhayPrajapati answered May 4, 2020 AbhayPrajapati comment Share Follow See 1 comment See all 1 1 comment reply DAWID15 commented Dec 21, 2021 i edited by DAWID15 Dec 21, 2021 reply Follow Share Even if you solve manually you’ll get T(n)= n(n+1)/2which is nothing but O(n^2) 0 votes 0 votes Please log in or register to add a comment.