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 $ f(n) = O(n^{ \log_{b}{(a - \epsilon)} }) $ for some constant $ \epsilon > 0 $ then $ T(n) = \Theta( n^{\log_b{a}} ) $

Case 2: Split/Recombine ~ Subproblems

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

Case 3: Split/Recombine Dominates (Root Heavy)

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

Revisiting Big O, Big Theta, Big Omega

Big O

When we say

$ f(n) = O(g(n)) $

what we mean is, there are some constants $ c > 0, n_0 > 0 $ such that

$ 0 \leq f(n) \leq c g(n) $

for all sufficiently large $ n \geq n_0 $

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

Example: $ 2n^2 = O(n^3) $

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:

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

Macro Convention

Macro convention - a set in a function represents an anonymous function in that set.

Note that this observation is the key mathematical underpinning of functional programming and function-based languages.

Example:

$ f(n) = n^3 + O(n^2) $

This means there is a function h(n) in the set O(N2) sucjh that f(n)= n3 + h(n)

they represent SOME func in that set

Can also read statements as having a lead "for all" and read the equal sign as "is":

$ n^2 + O(n) = O(n^2) $

is a true statement, but the reverse is not ture.

This means, for any f(n) in O(n), there exists some function g(n) in O(n^2) such that if you add n^2 to the function f(n), you get g(n).

Big Omega Notation

$ f(n) = \Omega( g(n) ) $

means f(n) is AT LEAST cost g(n),

$ \exists c > 0, n_0 > 0 : 0 \leq g(n) \leq f(n) $

for sufficiently large n.

Example: $ \sqrt{n} = \Omega(\log{n}) $

Big Theta Notation

$ f(n) = \Theta( g(n) ) = \Omega( g(n) ) \bigcap O(g(n)) $

means f(n) grows the same as g(n):

$ c1 g(n) \leq f(n) \leq c2 g(n) $