Master theorem: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(8 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== MASTER THEOREM ==
Let <math>a \ge 1</math> and <math>b > 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
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence


''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),
<math>T(n) = aT(\frac nb) + f(n)</math>,


where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.
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  ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>)
#If  <math>f(n) = O(n^{\log_b b a - \epsilon})</math> for some constant <math>\epsilon > 0</math>, then <math>T(n) = \Theta(n^{\log_b a})</math>.
#If <math>f(n) = \Theta(n^{\log_b a})</math>, then <math>T(n) = \Theta(n^{\log_b a} \lg n)</math>. <br>
#If <math>f(n) = \Omega(n^{\log_b a + \epsilon})</math> for some constant <math>\epsilon > 0</math>, and if <math>af(\frac nb) \le cf(n)</math> for some constant <math>c < 1</math> and all sufficiently large <math>n</math>, then <math>T(n) = \Omega(f(n))</math>.

Latest revision as of 23:26, 18 October 2014

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].