Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Solving a recurrence relation using iteration method

how to solve T(n) = T(n-1) + n using Iterative method and answer is theta(n^2)

like image 367
Santhosh Avatar asked Nov 24 '25 12:11

Santhosh


2 Answers

T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1+ 2 + ... + n = (n+1)n/2 = theta(n^2)


note the assumption that T(0) = 0 (you must have base for the recursion)
hope that what you have meant

like image 107
amit Avatar answered Nov 27 '25 13:11

amit


At times, you could also use characteristics equations method to solve recurrence relations. This involves determining Particular integral and total solution.

More information here: solving recurrence relations


Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!