EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2 1 Master Theorem
The Master Theorem provides “cookbook solutions” for recurrence relations of a certain form. More specifically, it provides asymptotic bounds for recurrences which describe the time complexity of divide-and-conquer algorithms which you have seen and may see in the future (e.g. mergesort, Karatsuba multiplication), though there are some divide-and-conquer algorithms for which the Master Theorem is not applicable.
Theorem 1.1 (The Master Theorem). Let T(n) = kT(n/b)+Θ(nd) for constants k,b,d (k,b > 1).
Copyright By PowCoder代写 加微信 powcoder
Θ(nd) T(n) = Θ(nd logn)
Θ(nlogb k)
The Master theorem is typically proved by constructing a recursion tree and using said recursion tree to sum the amount of work to be done. We provide a proof under the simplifying assumptions that n is a power of b and that the work done on an input of size X is exactly Xd.
Figure 1: An example of a recursion tree for T (n) = 3T (n/4) + cn2 (Source: CLRS)
Proof. Let T be the amount of work done by the algorithm and Ti be the amount of work in the
i-th level of the recursion tree. Then we have that T = logb n Ti. At the i-th level, there are ki i=0
problems each of size n/bi (by our simplifying assumption, our tree is a full, perfect k-ary tree). A problem of size X takes Xd work (by our simplifying assumption – if we did not have that, it would take Θ(Xd) work). We can compute the total amount of work done in the recursion as follows:
if k/bd < 1 if k/bd = 1 if k/bd > 1.
log n log n log n log n bbnbkibki
iddd Ti=kbi=nbd=n bd.
i=0 i=0 i=0 i=0
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2 We have three cases:
1. If k/bd = 1, then T = nd logb n k i = nd logb n 1 = nd(log n + 1) = nd log n + nd = i=0 bd i=0 b logb
Θ(nd log n) (aside: b is a constant, so log b is also a constant).
2. If k/bd < 1, then we have a geometric series logb n k i ≤ ∞ k i. You may observe
i=0 bd i=0bd
(or recall from calculus) that ∞ k i evaluates to a constant (using the assumption that
k/bd <1),sologbnk i =O(1). Thenobservethat1≤logbnk i sologbnk i =Ω(1)
i=0 bd i=0 bd i=0 bd which indicates logb n k i = Θ(1), and T = ndΘ(1) = Θ(nd).
3. If k/bd > 1, then we have another geometric series logb n k i = (k/bd)logb n+1−1 . Observe
i=0 bd (k/bd )−1
that k,b and d are constants, so logb n k i = Θ k logb n. From this, we have T =
nd · Θ k logb n = Θnd k logb n = Θnd klogb n = Θ(klogb n) = Θ(nlogb k).
The divide-and-conquer algorithms to which the Master Theorem applies have the following characteristics:
• When dividing a problem of size n into sub-problems, the number of sub-problems is constant. This is expressed by k being constant.
• When dividing a problem of size n into sub-problems, the size of sub-problems is constant. This is expressed by b being constant.
• The time taken to “recombine” the solutions to the sub-problems to obtain a solution for the original problem (usually the “conquer” part of the algorithm) is bounded above by some polynomial.
Example 1.2. Provide a big-O bound for T (n) = 2T (n/3) + 2n2.
Solution: Simplifying into form appropriate for Master Theorem we get 2n2 = Θ(n2)
and therefore
2/32 < 1, therefore T (n) = Θ(n2)
T (n) = 2T (n/3) + Θ(n2).
Example 1.3. Provide a big-O bound for T (n) = 4T (n/2) + 4n2.
Solution: Simplifying into form appropriate for Master Theorem we get 4n2 = Θ(n2)
and therefore
4/22 = 1, therefore T (n) = O(n2 log n)
T (n) = 4T (n/2) + Θ(n2).
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2 Example 1.4. Provide a big-O bound for T (n) = 6T (2n/3) + n4.
Example 1.5. Provide a big-O bound for T (n) = 2T (n/2) + 4.
2 Master Theorem with Log Factors
We can extend the Master Theorem to provide closed form asymptotic relations for recurrence which contain a logarithmic factor in the “recombination” term. Suppose you find that your recursive algorithm satisfies the following recurrence:
T (n) = k · T (n/b) + nd logw n,
where k ≥ 1,b > 1,d ≥ 0,w ≥ 0. Then T can be upper bounded in closed form as follows:
T (n) = 6T (2n/3) + Θ(n4) 6/(1.5)4 = 6/5.0625 > 1, therefore T(n) = Θ(nlog1.5 6)
T(n) = 2T(n/2) + Θ(1) = 2T(n/2) + Θ(n0). 2/20 = 2/1 > 1, therefore T(n) = Θ(nlog2 2) = Θ(n)
Θ(ndlogwn) T(n) = Θ(nd logw+1 n)
Θ(nlogb k)
iflogbk
This is a generalization of the Master Theorem in that if w = 0, then we obtain the Master Theorem (1.1). If you are interested, the (optional) derivation of the Master Theorem with log factors can be found at the bottom of the section notes.
Example 2.1. Provide a big-O bound for T (n) = 3T (n/4) + n4 log2 n.
Example 2.2. Provide a big-O bound for T (n) = 5T (n/2) + n2 log3 n.
Example 2.3. Provide a big-O bound for T (n) = 8T (n/2) + n3.
Solution: Wehavek=3,b=4,d=4,w=2;log43<1<3=d,soweareinthefirstcaseof the Master Theorem. T (n) = Θ(n4 log2 n).
Solution: Wehavek=5,b=2,d=2,w=3;log25>2=d,soweareinthethirdcaseof the Master Theorem. T (n) = Θ(nlog2 5).
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2
3 Karatsuba Algorithm
The Karatsuba algorithm is a divide-and-conquer algorithm for multiplying two n-digit integers A and B. This algorithm can be implemented on a computer by adjusting the algorithm to instead account for the representation of integers in binary (rather than decimal, the conventional representation). In fact, we can make the Karatsuba algorithm work for any base, not just 2 or 10. The changes will always be similar. In this discussion section, we will mainly focus on the Karatsuba algorithm and decimal integers. There is an example for how the Karatsuba algorithm works in the binary case after the discussion of the decimal case.
The basic idea is to split the decimal representations of A and B into two halves, multiply each pair of halves together recursively, and then use the distributive property (FOIL) to combine the results. Using a rather clever trick, we can do this in three multiplications rather than four, bringing the runtime down to O(nlog2 3) ≈ O(n1.585).
The algorithm works as follows: Write A and B as A=a·10n/2 +b
B = c · 10n/2 + d
where a and c are the higher-order n/2 digits of A and B, respectively, and b and d are the
lower-order n/2 digits of A and B. Substituting and using the distributive property, we have A · B = (a · 10n/2 + b) · (c · 10n/2 + d) = (a · c) · 10n + (a · d + b · c)10n/2 + b · d.
Note a few things:
1. The numbers a, b, c, d are all (approximately) n/2 digits long. Thus, each of the numbers
a·c,a·d+b·c,b·d are all (approximately) about n digits long.1
2. Multiplying by powers of 10 is efficient for a computer working in a base 10 system as it is just
a digit-shift (basically just appending 0s to the end of the number’s decimal representation).
3. Addition of two n-digit numbers can be done in O(n) time (e.g. via the usual grade-school method). Thus, if we already have the values of a·c, a·d+b·c, and b·d, we can compute the right-hand side (which is A · B) in O(n) time.
Now, if we were to simply compute a·b, a·d, b·c, and b·d recursively, we would get a runtime that obeys the recurrence T (n) = 4T (n/2) + O(n), which solves (by the Master Theorem) to T(n) = O(n2). That’s no better than the elementary school algorithm! (Worse, in fact, due to the larger constant factors.) However, knowing the values of a · c and b · d, we can save one multiplication by computing a·d+b·c as (a+b)·(c+d)−a·c−b·d. Thus, we actually have T (n) = 3T (n/2) + O(n), which solves to T (n) = O(nlog2 3).
1There are several details swept under the rug: if n is odd then the length of a,b,c,d is at most ⌈n/2⌉, and the additions a+b and c+d may have length ⌈n/2⌉+1. Most of the time these details do not change the overall analysis.
Solution: Wehavek=8,b=2,d=3,w=0;log28=3=d,soweareinthesecondcaseof the Master Theorem. T (n) = Θ(n3 log n)
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022
Algorithm 1 The Karatsuba algorithm for Decimal Multiplication Input: integers x, y, which are both n-digit numbers with n ≥ 1 Output: x·y
function Karatsuba(x, y)
// n here represents the number of digits in the decimal representation of x if n=1then
return x · y else
Write x as a·10n/2 +b
Write y as c·10n/2 +d
M1 ← Karatsuba(a, c)
M2 ← Karatsuba(b, d)
M3 ← Karatsuba(a + b, c + d)
return M1 ·10n +(M3 −M1 −M2)·10n/2 +M2
Example 3.1. Let’s multiply 3276 · 4143 using the Karatsuba algorithm. We write the numbers to be multiplied as
3276=3200+76=32·102 +76 4143=4100+43=41·102 +43.
Thismeansa=32,b=76,c=41,andd=43. Then
M1 =a·c=32·41=1312
M2 =b·d=76·43=3268
M3 =(a+b)·(c+d)=(32+76)·(41+43)=9072.
(Note that M1, M2, and M3 are computed recursively. However, we have omitted the steps here for the sake of brevity. You should work out these multiplications yourself to ensure that you understand how the algorithm works.)
The output of the algorithm is therefore
1312·104 +(9072−1312−3268)·102 +3268 = 13572468 .
3.1 A Binary Example
Karatsuba works exactly the same way in binary, only with the 10s replaced by 2s. Let’s multiply 11012 · 10112. (We’ll omit the subscript 2 for the rest of this example.) We have
1101=1100+01=11·22 +1 1011=1000+11=10·22 +11.
Soa=11,b=1,c=10,andd=11. Then
M1 =a·c=11·10=110
M2 =b·d=1·11=11
M3 =(a+b)·(c+d)=(11+1)·(10+11)=10100.
Discussion Notes 2
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2
(Again, M1, M2, and M3 are to be computed recursively.) The output is thus
110·24+(10100−110−11)·22+11= 10001111.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2 4 (Optional) Derivation of the Master Theorem with Log-Factors
The following is a derivation of the Master Theorem with log factors. A nice proof and expla- nation of the regular Master Theorem can be found at https://www.coursera.org/lecture/ algorithmic-toolbox/proof-of-the-master-theorem-7KR1r (may require registration). We’d recommend being comfortable with that before proceeding. As with all material labeled as ”op- tional” this will not be on any homework or exam (though understanding it could certainly help with related problems..).
Suppose you find that your recursive algorithm satisfies the following recurrence: T (n) = k · T (n/b) + nd logw n,
where k ≥ 1,b > 1,d ≥ 0,w ≥ 0. Then T can be upper bounded in closed form as follows:
Θ(ndlogwn) T(n) = Θ(nd logw+1 n)
Θ(nlogb k)
Recall that for any real a > 0, a geometric series can be evaluated as:
The total running time T is:
aN+1−1 a0 +a1 +a2 +···+aN = a−1
Ti = ki(n)d logw(n) bi bi
iflogbk
if a ̸= 1 N + 1 if a = 1
I.e., asymptotically it is Θ(a0) = Θ(1) (dominated by the first term) if a < 1, Θ(aN) (dominated by the last term) if a > 1, and equal to the number of terms if a = 1, thus Θ(N).
There are ki recursive calls at depth i, and each performs (n/bi)d logw(n/bi) work in addition to the recursive calls it makes. Define Ti to be the work performed at recursion depth i, then:
T = T0 + T1 + T2 + · · · + Tlogb n (1) = ki(n)d logw(n) (2)
0≤i≤logb n bi bi
≤ ki(n)dlogwn (3)
0≤i≤logb n bi
=ndlogwn (k)i (4)
0≤i≤logb n bd
If k/bd < 1 then the sum in (4) converges to some constant (Θ(1)), and we are in the first case:
= Θ(nd logw n) (5)
If k/bd = 1 then the sum in (4) is equal to the number of terms, namely logb n, and we are in the second case:
= Θ(nd logw+1 n) (6) 7
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 2
For the third case (k/bd > 1), we will use the fact that logw n grows more slowly than any polynomial inn. Pickd′ =d+ε
C1(k/bd′ )logb n for a constant C1. Continuing:
≤ C0C1 · nd′ (k/bd′ )logb n = C0C1 · klogb n
= C0C1 · blogb k·logb n
= C0C1nlogb k = Θ(nlogb k) And we are in the third case.
0≤i≤logb n bi =C0nd′ (k/bd′)i
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com