CSOR W4231.002 Notes on the Master Theorem (rev: Jan 2017)
Often when analyzing a divide & conquer algorithm, we obtain a recurrence for its running time of the following form
T(n) = aT(nb)+cnk (1)
In words, on input size n, the algorithm generates a subproblems, each of size n/b; combining these subproblems to obtain the overall solution requires time polynomial in n, specifically cnk.
Copyright By PowCoder代写 加微信 powcoder
Such recurrences appear frequently so it is useful to know asymptotic bounds for them in terms of a,b and k (as we will see, c does not affect the asymptotic solution). To this end, we will analyze the recursion tree for this recurrence (see Figure 1).
c(n/b)k c(n/b)k
level 1 level 2
level i …
level ⎡logbn⎤
ai c(n/bi)k
Figure 1: The recursion tree for recurrence (1). a is the branching factor, b is the factor by which the input size shrinks at every recursive call and cnk is the time required to combine the solutions to the subproblems into the overall solution for input size is n. The smallest possible size of a subproblem is O(1); typically, solving input instances of small constant size requires constant time c.
• a is the branching factor of the tree: every subproblem gives rise to a new subproblems at the next level of the tree; thus
1. at level 1, we have a subproblems
2. at level 2, each of the a subproblems in level 1 gives rise to a new subproblems; therefore
there are a total of a2 subproblems
3. at level 3, each of the a2 subproblems in level 2 generates a new subproblems; therefore there
are a total of a3 subproblems
4. at the level i, there are ai subproblems
• b is the factor by which the input size shrinks at every level; thus
1. at level 1, the input size of each subproblem shrinks by a factor of b, that is, from n it now
becomes n/b;
2. at level 2, the input size of each subproblem further shrinks by a factor of b, that is, from n/b
it now becomes (n/b)/b = n/b2;
3. at level 3, the input size of each subproblem again shrinks by a factor of b, hence becomes
(n/b2)/b = n/b3;
4. at level i, the size of each subproblem is n/bi
⇒ at level i, the amount of work spent on each subproblem of size n/bi is 1: cnk
bi ⇒ at level i, the work spent on all subproblems is
We need one more observation before we can compute the total work spent on the recursion tree. Fact 1 The depth of the tree in Figure 1 is ⌈logb n⌉ levels.
Proof. The last level of the recursion tree, call it d, consists of subproblems of size 1. Since at level i subproblems have size n/bi, we are looking for d such that
n =1⇒d=logbn bd
kai acbi =cnbk
Since d is an integer, d = ⌈logb n⌉.
We are now ready to derive a bound for T(n) by computing the total work spent on this recursion
tree, which is given by the sum of the work spent at each level of the tree:
⌈log n⌉ ⌈log n⌉
b a b a
T(n) = cn bk =cn bk (2)
Note that T (n) depends on a sum over ⌈logb n⌉ terms of a geometric progression with common ratio a/bk and initial value (a/bk)0 = 1. Depending on the value of the common ratio a/bk, this sum will exhibit the following behavior:
1. a =1;inthiscase,wehave bk
⌈log n⌉ ⌈log n⌉ bab i
bk = 1 = ⌈logb n⌉ + 1 = Θ(logb n) (3) i=0
2. a < 1; in this case, you can show that the sum of the entire geometric progression is dominated
by its initial value, that is,
⌈log n⌉ b a a i0
1Recall that the amount of work spent on combining the subproblems when the the input size is n is cnk.
= Θ(1) (4)
a > 1; again, you can show that the sum of the entire geometric progression is now dominated by bk
its last term, that is,
⌈log n⌉ b
Theorem 1 (Master theorem) If T(n) = aT(⌈n/b⌉)+O(nk) for some constants a > 0, b > 1, k ≥ 0, then
a =Θa i
Plugging back equations (3), (4), (5) into equation (2), we summarize our findings in the following
logbn bklogb n
=Θn (5)
O(nlogba) ,ifa>bk O(nklogn) ,ifa=bk
O(nk) ,ifa