Math Fundamentals18 sections · 814 units
Open in Course

Recurrence Relations

Recursive algorithm analysis

Recursive algorithms have time complexity described by recurrence relations. For example, merge sort has T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n).

This says: divide the problem into two halves (each taking T(n/2)T(n/2) time) and spend O(n)O(n) time merging. Solving this recurrence gives T(n)=O(nlog⁡n)T(n) = O(n \log n).

Solving recurrences requires algebraic manipulation: expanding terms, factoring, finding patterns, and applying formulas like the Master Theorem.