10. Master Theorem

06/03/23

Consider recurrence relations of the form $T(n) = a T(n/b) + f(n)$

• Designed for divide and conquer in which problems are divided into a instances of a problem of size $n/b$
• Aim is to be quickly express the big-Oh family behaviour of T(n) for various cases of the values of a and b, and the scaling behaviour of f(n)
• No proof needed, just need to learn it and how to apply it

Cases

$T(n) = a T(n/b) + f(n)$ Results are split into 3 cases, according to comparing the growth rate of f(n) to $n^{(\log_{b}{a})}$

• Case 1: $f(n)$ grows slower. Recurrence term dominates. (Solution ignores f)
• Case 2: $f(n)$ grows same - up to log factors - mix of recurrence with $a,b$, and also the $f(n)$ term
• Case 3: $f(n)$ grows faster. Solution ignores recurrence terms and $a,b$