Unformatted text preview:

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

PSU CSE 565 - Solving Recurrences

Download Solving Recurrences
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Solving Recurrences and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Solving Recurrences 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?