This Repository contains topics related to recurrence relation. Recurrence relations can vary greatly in complexity and form depending on the specific sequence or problem being modeled. They are often used in algorithm analysis, dynamic programming, and solving various types of mathematical and computational problems.
There are several methods to solve recurrence relations, depending on their complexity and form. Here are some common techniques:
Direct Substitution
Recursive Tree Method
Master Theorem
| Lectures | Video Link | Video PDF |
|---|---|---|
| 1) DAC / How to write recurrence relation |  |
 |
| 2) Substitution Method T(n) = 3T(n-1) | |
|
| 3) Substitution Method T(n) = 2T(n-1) -1 | |
|
| 4) Substitution Method T(n) = T(n-1) +n(n-1) | |
|
| 5) Substitution Method T(n) = n+T(n-1) | |
|
| 6) Recurrence Tree Method T(n) =2T(n/2) +n | |
|
| 7) Recurrence Tree Method T(n) = T(n/3) +T(2n/3) +n | |
|
| 8) Recursive Tree Method T(n) = T(n-1) +log n | |
|
| 9) Recursive Tree Method T(n) = 2T(n-1) + 1 | |
|
| 10) Master Theorem | |
|
| 11) Master Theorem 2 | |
|
| 12) Master Theorem 3 | |
|
| 13) Space Complexity of Recursive Algorithm | |
|
| 14) Space Complexity of Recursive Algorithm 2 | |
|
