Master theorem

From Algowiki
Jump to: navigation, search

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

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

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

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