master method

To evaluate the the divide and conquer algorithm

1. Base case: $T(n) leq $ a constant for all sufficiently small n

2. For all larger n:

   $$T(n) leq aT(n/b) + O(n{^d})$$

   where:

   ​ a = number of recursive calls (>=1)

   ​ b = input size shrinkage factor(>1)

   ​ d = exponent in running time of “combine step” (>=0)

   ​ [a, b, d independent of n]

$$begin{equation}T(n) = begin{cases} O(n^dlog n) &mbox{if a = b^d} \ O(n^d) &mbox{if a < b^d} \ O(n^{log_b a}) &mbox{if a > b^d} end{cases} end{equation}$$

1. To memorize:

   1	Tn = (logb(a) == d) ? n^d*log(n) : max(n^d, n^(logb(a)))

2. Intuition:

   1. In level j, the number of subproblems is $a^j$, the size of one subproblem is $n/b^j$

   2. The amount work to be done in the level j is $a^{j}(n/b^{j})^d = n^{d} (a/b^{d})^{j}$

   3. Here $n^d​$ is a constant amount of work in each level, a is rate of subproblem proliferation (RSP), $b^d​$ is rate of work shrinkage (RWS).

   4. If RSP < RWS, the amount of work decreases as level increases, so the the most amount of work are done in the root. Total work: $n^d$

      If RSP = RWS, the amount of work in every level keeps the same ($n^d$), so the total amount of work is nums of level * works every level. i.e. $n^dlog_bn$

      If RSP > RWS, the amount of work increases as level increases, so the most amount of work are done in the leaves of the tree. Total work: the number of the leaves. i.e. $a^{log_bn} = n^{log_ba}$