Master theorem: Difference between revisions
Jump to navigation
Jump to search
| (9 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
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 | |||
<math>T(n) = aT(\frac nb) + f(n)</math>, | |||
where we interpret | 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. | ||
#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.
- 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].
- If [math]\displaystyle{ f(n) = \Theta(n^{\log_b a}) }[/math], then [math]\displaystyle{ T(n) = \Theta(n^{\log_b a} \lg n) }[/math].
- 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].