Which theorem provides a standardized way to solve recurrence relations of the form T(n) = aT(n/b) + f(n)?
Show answer
Master Theorem
The Master Theorem compares the growth of f(n) with the function n^(log_b a). Depending on which part dominates, it provides a solution for the overall asymptotic complexity of the recurrence.
Also asked as:
- What theorem is used to determine the asymptotic complexity of recurrences that follow the form T(n) = aT(n/b) + f(n)?