Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 2 Prof. Erik Demaine Day 3 Introduction to Algorithms L2.2 Solving recurrences ? The analysis of merge sort from Lecture 1 required us to solve a recurrence. ? Recurrences are like solving integrals, differential equations, etc. o Learn a few tricks. ? Lecture 3: Applications of recurrences. Day 3 Introduction to Algorithms L2.3 Substitution method 1. Guess the form of the solution. 2. Verify by induction. 3. Solve for constants. The most general method: Example: T(n) = 4T(n/2) + n ? [Assume that T(1) = Θ(1).] ? Guess O(n 3 ) . (Prove O and ? separately.) ? Assume that T(k) ≤ ck 3 for k < n . ? Prove T(n) ≤ cn 3 by induction. Day 3 Introduction to Algorithms L2.4 Example of substitution 3 33 3 3 ))2/(( )2/( )2/(4 )2/(4)( cn nnccn nnc nnc nnTnT ≤ ??= += +≤ += desired – residual whenever (c/2)n 3 – n ≥ 0, for example, if c ≥ 2 and n ≥ 1. desired residual Day 3 Introduction to Algorithms L2.5 Example (continued) ? We must also handle the initial conditions, that is, ground the induction with base cases. ? Base: T(n) = Θ(1) for all n < n 0 , where n 0 is a suitable constant. ? For 1 ≤ n < n 0 , we have “Θ(1)” ≤ cn 3 , if we pick c big enough. This bound is not tight! Day 3 Introduction to Algorithms L2.6 A tighter upper bound? We shall prove that T(n) = O(n 2 ). Assume that T(k) ≤ ck 2 for k < n: )( 4 )2/(4)( 2 nO ncn nnTnT = +≤ += Wrong! We must prove the I.H. 2 2 )( cn ncn ≤ ??= for no choice of c > 0. Lose! [ desired – residual ] Day 3 Introduction to Algorithms L2.7 A tighter upper bound! IDEA: Strengthen the inductive hypothesis. ? Subtract a low-order term. Inductive hypothesis: T(k) ≤ c 1 k 2 – c 2 k for k < n. )( 2 )2/()2/((4 )2/(4)( 2 2 1 22 2 1 2 2 1 2 2 1 ncnc nncncnc nncnc nncnc nnTnT ?≤ ???= +?= +?≤ += if c 2 > 1. Pick c 1 big enough to handle the initial conditions. Day 3 Introduction to Algorithms L2.8 Recursion-tree method ? A recursion tree models the costs (time) of a recursive execution of an algorithm. ? The recursion tree method is good for generating guesses for the substitution method. ? The recursion-tree method can be unreliable, just like any method that uses ellipses (…). ? The recursion-tree method promotes intuition, however. Day 3 Introduction to Algorithms L2.9 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : Day 3 Introduction to Algorithms L2.10 Example of recursion tree T(n) Solve T(n) = T(n/4) + T(n/2) + n 2 : Day 3 Introduction to Algorithms L2.11 Example of recursion tree T(n/4) T(n/2) n 2 Solve T(n) = T(n/4) + T(n/2) + n 2 : Day 3 Introduction to Algorithms L2.12 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : n 2 (n/4) 2 (n/2) 2 T(n/16) T(n/8) T(n/8) T(n/4) Day 3 Introduction to Algorithms L2.13 Example of recursion tree (n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 (n/4) 2 (n/2) 2 Θ(1) … Solve T(n) = T(n/4) + T(n/2) + n 2 : n 2 Day 3 Introduction to Algorithms L2.14 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : (n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 (n/4) 2 (n/2) 2 Θ(1) … 2 n n 2 Day 3 Introduction to Algorithms L2.15 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : (n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 (n/4) 2 (n/2) 2 Θ(1) … 2 16 5 n 2 n n 2 Day 3 Introduction to Algorithms L2.16 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : (n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 (n/4) 2 Θ(1) … 2 16 5 n 2 n 2 256 25 n n 2 (n/2) 2 … Day 3 Introduction to Algorithms L2.17 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n 2 : (n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 (n/4) 2 Θ(1) … 2 16 5 n 2 n 2 256 25 n ( ) ( )( ) 1 3 16 5 2 16 5 16 5 2 L++++n … Total = = Θ(n 2 ) n 2 (n/2) 2 geometric series Day 3 Introduction to Algorithms L2.18 The master method The master method applies to recurrences of the form T(n) = aT(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive. Day 3 Introduction to Algorithms L2.19 Three common cases Compare f (n) with n log b a : 1. f (n) = O(n log b a – ε ) for some constant ε > 0. ? f (n) grows polynomially slower than n log b a (by an n ε factor). Solution: T(n) = Θ(n log b a ) . 2. f (n) = Θ(n log b a lg k n) for some constant k ≥ 0. ? f (n) and n log b a grow at similar rates. Solution: T(n) = Θ(n log b a lg k+1 n) . Day 3 Introduction to Algorithms L2.20 Three common cases (cont.) Compare f (n) with n log b a : 3. f (n) = ?(n log b a + ε ) for some constant ε > 0. ? f (n) grows polynomially faster than n log b a (by an n ε factor), and f (n) satisfies the regularity condition that af(n/b) ≤ cf(n) for some constant c < 1. Solution: T(n) = Θ( f (n)) . Day 3 Introduction to Algorithms L2.21 Examples Ex. T(n) = 4T(n/2) + n a = 4, b = 2 ? n log b a = n 2 ; f (n) = n. CASE 1: f (n) = O(n 2–ε ) for ε = 1. ∴ T(n) = Θ(n 2 ). Ex. T(n) = 4T(n/2) + n 2 a = 4, b = 2 ? n log b a = n 2 ; f (n) = n 2 . CASE 2: f (n) = Θ(n 2 lg 0 n), that is, k = 0. ∴ T(n) = Θ(n 2 lg n). Day 3 Introduction to Algorithms L2.22 Examples Ex. T(n) = 4T(n/2) + n 3 a = 4, b = 2 ? n log b a = n 2 ; f (n) = n 3 . CASE 3: f (n) = ?(n 2+ ε ) for ε = 1 and 4(cn/2) 3 ≤ cn 3 (reg. cond.) for c = 1/2. ∴ T(n) = Θ(n 3 ). Ex. T(n) = 4T(n/2) + n 2 /lgn a = 4, b = 2 ? n log b a = n 2 ; f (n) = n 2 /lgn. Master method does not apply. In particular, for every constant ε > 0, we have n ε = ω(lgn). Day 3 Introduction to Algorithms L2.23 General method (Akra-Bazzi) )()/()( 1 nfbnTanT k i ii += ∑ = Let p be the unique solution to ( ) /ba k i p ii 1 1 = ∑ = Then, the answers are the same as for the master method, but with n p instead of n log b a . (Akra and Bazzi also prove an even more general result.) . Day 3 Introduction to Algorithms L2.24 f (n/b) Idea of master theorem f (n/b) f (n/b) Τ(1) … Recursion tree: … f (n) a f (n/b 2 ) f (n/b 2 ) f (n/b 2 ) … a h = log b n f (n) af(n/b) a 2 f (n/b 2 ) … #leaves = a h = a log b n = n log b a n log b a Τ(1) Day 3 Introduction to Algorithms L2.25 f (n/b) Idea of master theorem f (n/b) f (n/b) Τ(1) … Recursion tree: … f (n) a f (n/b 2 ) f (n/b 2 ) f (n/b 2 ) … a h = log b n f (n) af(n/b) a 2 f (n/b 2 ) … n log b a Τ(1) CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight. ASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight. Θ(n log b a ) Day 3 Introduction to Algorithms L2.26 f (n/b) Idea of master theorem f (n/b) f (n/b) Τ(1) … Recursion tree: … f (n) a f (n/b 2 ) f (n/b 2 ) f (n/b 2 ) … a h = log b n f (n) af(n/b) a 2 f (n/b 2 ) … n log b a Τ(1) CASE 2: (k = 0) The weight is approximately the same on each of the log b n levels. ASE 2: (k = 0) The weight is approximately the same on each of the log b n levels. Θ(n log b a lg n) Day 3 Introduction to Algorithms L2.27 f (n/b) Idea of master theorem f (n/b) f (n/b) Τ(1) … Recursion tree: … f (n) a f (n/b 2 ) f (n/b 2 ) f (n/b 2 ) … a h = log b n f (n) af(n/b) a 2 f (n/b 2 ) … n log b a Τ(1) CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight. ASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight. Θ( f (n)) Day 3 Introduction to Algorithms L2.28 Conclusion ? Next time: applying the master method. ? For proof of master theorem, see CLRS. Day 3 Introduction to Algorithms L2.29 Appendix: geometric series 1 1 1 2 x xx ? =+++ L for |x| < 1 1 1 1 1 2 x x xxx n n ? ? =++++ + L for x ≠ 1 Return to last slide viewed.