master theorem

master_theorem.md

A problem is divided into a subproblem, each problem has size n/b
and combine these answers in O(n^d) time.

If T(n) = aT(ceiling(n/b)) + O(n^d) for some constant 

a > 0, b > 1, and d >= 0, then

T(n) = O(n^d) if d > log_b a
T(n) = O(n^d log n) if d = log_b a
T(n) = O(n^log_b a) if d < log_b a

Proof. Assuming n is power of b. This will not influcence the final bound

Notice that the size of the subproblem decreases by a factor
of b with each level of recursion, therefore reaches the base case
after log_b n levels. This is the height of the recursion tree. Its
branching factor is a, so the kth level of the tree is made up of a^k
subproblems, each of size n/b^k. The total work done at this level is

a^k x O(n/b^k)^d = O(n^d) x (a/b^d)^k

as k goes from 0 (the root) to log_b n (the leaves), these numbers form
a geometric seris with ratio a/b^d.

1. The ratio is less than 1
   Then the seris is decreasing, and its sum is just given by its first term, O(n^d)
2. The ration is greater than 1.
   The seris is increasing and its sum is given by its last term, O(n^log_b a):

n^d (a/b^d)^{log_b n} = n^d (a^{log_b n} / (b^{log_b n}^d)) = a^{(log_b n)(log_b a)} = n^log_b a.

3. The ratio is exactly 1.
   In this case all O(log n) terms of the series are equal to O(n^d).

see https://gist.github.com/nickyfoto/f0cd27a7b786858314be7960577cb8c6

why log_b n = (log_a n ) (log_b a)