Register

Solve the recurrence Relation

• retagged by
308 views

1 Answer

Best answer
5 votes
5 votes

This is easy,

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

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

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

       ............................

       ................................

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

       Put k = n - 1

       = T(1) + 2 + 3 + 4 + 5 + ...................... + n

       = 1 + 2 + 3 + 4 + 5 + ............................ + n

       = n(n+1) / 2

        = O(n^2) 

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
rexritz asked Aug 13, 2023
303 views
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
0 votes
0 votes
1 answer
3
im.raj asked May 27, 2016
341 views
Solve The Recurrence Relation
T(n) = 1, if n = 1 = T(n-1) + 2^n , otherwise
T(n) = 1, if n = 1 = T(n-1) + 2^n , otherwise
User Avatar
0 votes
0 votes
1 answer
4
prateekdwv asked Mar 24, 2016
466 views
Solve the recurrence relation $B(n) = 3B(n/log_2(n))+\theta(n)$
What is the solution of following recurrence relation. $B(2) = 1$ $B(n) = 3B(n/\log_2(n))+\Theta(n)$​
What is the solution of following recurrence relation.$B(2) = 1$$B(n) = 3B(n/\log_2(n))+\Theta(n)$​
User Avatar
Link Copied!