9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Adam Smith Algorithm Design and Analysis LECTURE 12 Solving Recurrences • Master Theorem9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Review Question: Exponentiation Problem: Compute a b, where b ∈ N is n bits long. Question: How many multiplications? a b = a b/2 ⋅ a b/2 if b is even; a (b–1)/2 ⋅ a (b–1)/2 ⋅ a if b is odd. Divide-and-conquer algorithm: T(b) = T(b/2) + Θ(1) ⇒ T(b) = Θ(log b) = Θ(n) . Naive algorithm: Θ(b) = Θ(2n) (exponential in the input length!) Naive algorithm:9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. So far: 2 recurrences • Mergesort; Counting Inversions T(n) = 2 T(n/2) + Θ(n) = Θ(n log n) • Binary Search; Exponentiation T(n) = 1 T(n/2) + Θ(1) = Θ(log n) Master Theorem: method for solving recurrences.9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. The master method The master method applies to recurrences of the form T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive, that is f (n) >0 for all n > n0.9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Three common cases Compare f (n) with nlogba: 1. f (n) = O(nlogba – ε) for some constant ε > 0. • f (n) grows polynomially slower than nlogba (by an nε factor). Solution: T(n) = Θ(nlogba) .9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Three common cases Compare f (n) with nlogba: 1. f (n) = O(nlogba – ε) for some constant ε > 0. • f (n) grows polynomially slower than nlogba (by an nε factor). Solution: T(n) = Θ(nlogba) . 2. f (n) = Θ(nlogba lgkn) for some constant k ≥ 0. • f (n) and nlogba grow at similar rates. Solution: T(n) = Θ(nlogba lgk+1n) .9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Three common cases (cont.) Compare f (n) with nlogba: 3. f (n) = Ω(nlogba + ε) for some constant ε > 0. • f (n) grows polynomially faster than nlogba (by an nε factor), and f (n) satisfies the regularity condition that a f (n/b) ≤ c f (n) for some constant c < 1. Solution: T(n) = Θ( f (n) ) .9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a f (n) a f (n/b) a2 f (n/b2) …9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a h = logbn f (n) a f (n/b) a2 f (n/b2) …9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. nlogbaΤ (1) f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a h = logbn f (n) a f (n/b) a2 f (n/b2) #leaves = ah = alogbn = nlogba …9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a h = logbn f (n) a f (n/b) a2 f (n/b2) CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight. Θ(nlogba) … nlogbaΤ (1)9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a h = logbn f (n) a f (n/b) a2 f (n/b2) CASE 2: (k = 0) The weight is approximately the same on each of the logbn levels. Θ(nlogbalg n) … nlogbaΤ (1)9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. f (n/b) Idea of master theorem f (n/b) f (n/b) Τ (1) Recursion tree: … f (n) a f (n/b2) f (n/b2) f (n/b2) … a h = logbn f (n) a f (n/b) a2 f (n/b2) … CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight. nlogbaΤ (1) Θ( f (n))9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Examples EX. T(n) = 4T(n/2) + n a = 4, b = 2 ⇒ nlogba = n2; f (n) = n. CASE 1: f (n) = O(n2 – ε) for ε = 1. ∴ T(n) = Θ(n2).9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Examples EX. T(n) = 4T(n/2) + n a = 4, b = 2 ⇒ nlogba = n2; f (n) = n. CASE 1: f (n) = O(n2 – ε) for ε = 1. ∴ T(n) = Θ(n2). EX. T(n) = 4T(n/2) + n2 a = 4, b = 2 ⇒ nlogba = n2; f (n) = n2. CASE 2: f (n) = Θ(n2lg0n), that is, k = 0. ∴ T(n) = Θ(n2lg n).9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Examples EX. T(n) = 4T(n/2) + n3 a = 4, b = 2 ⇒ nlogba = n2; f (n) = n3. CASE 3: f (n) = Ω(n2 + ε) for ε = 1 and 4(n/2)3 ≤ cn3 (reg. cond.) for c = 1/2. ∴ T(n) = Θ(n3).9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Examples EX. T(n) = 4T(n/2) + n3 a = 4, b = 2 ⇒ nlogba = n2; f (n) = n3. CASE 3: f (n) = Ω(n2 + ε) for ε = 1 and 4(n/2)3 ≤ cn3 (reg. cond.) for c = 1/2. ∴ T(n) = Θ(n3). EX. T(n) = 4T(n/2) + n2/lg n a = 4, b = 2 ⇒ nlogba = n2; f (n) = n2/lg n. Master method does not apply. In particular, for every constant ε > 0, we have nε = ω(lg n).Notes • Reference on Master Th’m to be posted on web • Master Th’m generalized by Akra and Bazzi to cover many more recurrences: where • See http://www.dna.lth.se/home/Rolf_Karlsson/akrabazzi.ps !9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. T (n) = f(n) +k!i=1aiT (bin + hi(n))hi(n) = O(nlog2n)9/22/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova. Multiplying large integers • Given n-bit integers a, b (in binary), compute c=ab • Naïve (grade-school) …
View Full Document