Content deleted Content added
Oops, intended deeper undo. 50kb of formatting junk and off-topic Python code (why??)( |
Ninjagecko (talk | contribs) reverting my changes |
||
Line 29:
The Master theorem allows us to easily calculate the running time of such a recursive algorithm in [[Big O notation|Θ-notation]] without doing an expansion of the recursive relation above.
== Generic
The Master Theorem sometimes gives us asymptotically tight bounds to recurrences of the following form, commonly found in many [[Divide_and_conquer_algorithm|divide-and-conquer algorithms]]:
:<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math> where <math>a \in \mathbb{N} \mbox{, } 1 < b \in \mathbb{R}</math>▼
:<math>work(n) = \#SubProbs * work(\frac{n}{b}) + splitwork(n) </math>, where <math>n</math> is the problem size, <math>\frac{n}{b}</math> is the subproblem size, and splitwork is the work required to split the problem into <math>a</math> problems of size <math>1/b</math>
More formally:
▲:<math>T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)</math> where <math>a \in \mathbb{N} \mbox{, } 1 < b \in \mathbb{R}</math>
*''n'' is the size of the problem.
Line 41 ⟶ 44:
*''f'' (''n'') is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.
The Master Theorem says the following: Whenever we have a recurrence of this form, we can consider it as occurring in one of three regimes, based on how the work to split/recombine the problem relates to the special quantity <math>log_b a</math>, which we can call the critical exponent <math>c_{crit}</math>. (Below we use standard [[big O notation]].)
:<math>c_{crit} = log_b a = log(\#\text{subproblems}) log(\text{relative subproblem size})</math>
=== Case 1 ===▼
{| class="wikitable"
|-
! width=10|Case
! width=200|Description
! width=300|Condition on <math>f(n)</math> in relation to <math>c_{crit}</math>, i.e. <math>log_b a</math>
! width=350|Master Theorem bound
|-
:<math>T(n)= \Theta\left( n^{\log_b a} \right)</math>▼
! 1
==== Example ====▼
| Work to split/recombine the problem is dwarfed by the work of further recursive subproblems.
i.e. the recursion tree is leaf-heavy
| This occurs when <math>f(n)</math> is asymptotically upper-bounded by a lesser polynomial in <math>O(n^{c_{crit}-\epsilon})</math>, less than the critical polynomial. That is, any polynomial with a strictly smaller exponent, i.e. <math>f(x) \in O(n^c)</math> such that <math>c < c_{crit}</math>.
For example, if <math>log_b a</math> were 1/2, then all <math>f(x) \in O(n^c)</math> where <math>c<1/2</math> would fall into this regime.
| The splitting work can be ignored, and the total is asymptotically dominated by the leaves.
|-
! 2
| Work to split/recombine the problem is comparable to the work of further recursive subproblems.
| This occurs when <math>f(n)</math> is asymptotically rangebound by exactly the critical polynomial, times any number of optional logs <math>\Theta(n^{c_{crit}} log^{k} n)</math> for any <math>k>0</math>.
For example, if <math>f(x) \in \Theta(n^{c_{crit}})</math> (k is 0), or if <math>f(x) \in \Theta(n^{c_{crit}} log n)</math> (k is 1), etc.
| The <math>log(n)</math> term gets augmented by a single power. Whereas the splitting term previously was <math>f(x) \in \Theta(n^{c_{crit}} log^{k} n)</math>, <math>T(n)</math> now becomes:
|-
! 3
| Work to split/recombine the problem dominates the work of further recursive subproblems.
i.e. the recursion tree is root-heavy.
| This occurs when <math>f(x)</math> is asymptotically lower-bounded by a greater polynomial in <math>\Omega\left( n^{c_{crit}+\epsilon} \right)</math>, greater than the critical polynomial. That is, any polynomial with a strictly larger exponent, i.e. <math>f(x) \in \Omega(n^c)</math> such that <math>c > c_{crit}</math>.
| This doesn't necessarily tell us anything. If we furthermore know that
:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for some constant <math>k < 1</math> and sufficiently large <math>n</math> (often called the ''regularity condition'')▼
then we know that the total is asymptotically dominated by the splitting term <math>f(x)</math>:
|}
▲==== Case 1 Example ====
:<math>T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2</math>
Line 68 ⟶ 114:
(indeed, the exact solution of the recurrence relation is <math>T(n) = 1001 n^3 - 1000 n^2</math>, assuming <math>T(1) = 1</math>).
==== Case 2 Example ====
▲:<math>T(n)= \Theta\left( n^{c} \log^{k+1} n \right)</math>
<math>T(n) = 2 T\left(\frac{n}{2}\right) + 10n</math>
Line 96 ⟶ 132:
(This result is confirmed by the exact solution of the recurrence relation, which is <math>T(n) = n + 10 n\log_2 n</math>, assuming <math>T(1) = 1</math>.)
==== Case 3 Example ====
▲:<math>a f\left( \frac{n}{b} \right) \le k f(n)</math> for some constant <math>k < 1</math> and sufficiently large <math>n</math> (often called the ''regularity condition'')
▲:<math>T\left(n \right) = \Theta\left(f(n) \right)</math>
:<math>T(n) = 2 T\left(\frac{n}{2}\right) + n^2</math>
| |||