Master theorem

MASTER THEOREM

Let [math]\displaystyle{ a \ge 1 }[/math] and [math]\displaystyle{ b \gt 1 }[/math] be constants, let [math]\displaystyle{ f(n) }[/math] be a function, and let [math]\displaystyle{ T(n) }[/math] be defined on the nonnegative integers by the recurrence

[math]\displaystyle{ T(n) = aT(\frac nb) + f(n) }[/math],

where we interpret [math]\displaystyle{ n/b }[/math] to mean either [math]\displaystyle{ \lfloor \frac nb \rfloor or \lceil \frac nb \rceil }[/math]. Then [math]\displaystyle{ T(n) }[/math] can be bounded asymptotically as follows.

1. If [math]\displaystyle{ f(n) = O(n^{\log_b b a - \epsilon}) }[/math] for some constant [math]\displaystyle{ \epsilon \gt 0 }[/math], then [math]\displaystyle{ T(n) = \Theta(n^{\log_b a}) }[/math].
2. If [math]\displaystyle{ f(n) = \Theta(n^{\log_b a}) }[/math], then [math]\displaystyle{ T(n) = \Theta(n^{\log_b a} \lg n) }[/math].
   
3. If [math]\displaystyle{ f(n) = \Omega(n^{\log_b a + \epsilon}) }[/math] for some constant [math]\displaystyle{ \epsilon \gt 0 }[/math], and if [math]\displaystyle{ af(\frac nb) \le cf(n) }[/math] for some constant [math]\displaystyle{ c \lt 1 }[/math] and all sufficiently large [math]\displaystyle{ n }[/math], then [math]\displaystyle{ T(n) = \Omega(f(n)) }[/math].