View source for Divide and Conquer/Master Theorem

==Statement of Master Theorem==

The Master Theorem is used to analyze three distinct cases for divide-and-conquer recurrences:

'''Case 1: Subproblems Dominate (Leaf-Heavy)'''

If <math>f(n) = O(n^{ \log_{b}{(a - \epsilon)} })</math> for some constant <math>\epsilon > 0</math> then <math>T(n) = \Theta( n^{\log_b{a}} )</math>

'''Case 2: Split/Recombine ~ Subproblems'''

If <math>f(n) = \Theta( n^{\log_b{a}} \log^k{(x)} )</math>, then <math>T(n) = \Theta( n^{\log_b{a}} \log^{k+1} {n} )</math> (note that usually <math>k=0</math>)

'''Case 3: Split/Recombine Dominates (Root Heavy)'''

If <math>f(n) = \Omega( n^{\log_b{(a+\epsilon)}} )</math> for some constant <math>\epsilon > 0</math> , and if <math>a f(n/b) \leq cf(n)</math> for some <math>c < 1</math>, then <math>T(n) = \Theta( f(n) )</math>

==Revisiting Big O, Big Theta, Big Omega==

===Big O===

When we say 

<math>
f(n) = O(g(n))
</math>

what we mean is, there are some constants <math>c > 0, n_0 > 0</math>  such that

<math>
0 \leq f(n) \leq c g(n)
</math>

for all sufficiently large <Math>n \geq n_0</math>

We say that f(n) is ''bounded above'' by g(n).

Example: <math>2n^2 = O(n^3)</math>

Big O corresponds roughly to less than or equal to 

Note that this equal sign notation is NOT symmetric - n^3 != O(n^2)

We can also think about a ''set definition'' - f(n) is in some set of functions that are like g(n)

O(g(n)) can be defined as a set of functions h(n) such that:

<math>
{h(n) : \exist c > 0, n_0, 0 \leq f(n) \leq c g(n)}
</math>

==Examples==