Introduction to algorithms 6.046J/18.401J/SMA5503 Lecture 2 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 2 Prof. Erik Demaine
Solving recurrences The analysis of merge sort from Lecture I required us to solve a recurrence ● Recurrences are like solving integrals erential equations, etc o Learn a few tricks Lecture 3: Applications of recurrences Day 3 Introduction to Algorithms
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
Substitution method The most general method 1 Guess the form of the solution 2. Verify by induction 3. Solve for constants Example: T(n)=4T(n/2)+n ASsume that T(1=0(1). Guess O(n).(Prove O and Q2 separately. Assume that t(k)sck for k<n Prove T(n)s cn by induction Day 3 Introduction to Algorithms L2.3
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(n3) . (Prove O and Ω separately.) • Assume that T(k) ≤ ck3 for k < n . • Prove T(n) ≤ cn3 by induction
Example of substitution T(n)=47(n/2)+n ≤4c(n/2)3+n =(c/2n3+n cn3-((c/2)n3-n+ desired-residual <Cn3← desire whenever(c/2)n3-n20, for example fc≥2andn≥1 residue Day 3 Introduction to Algorithms L24
Day 3 Introduction to Algorithms L2.4 Example of substitution 3 3 3 3 3 (( / 2) ) ( / 2) 4 ( / 2) ( ) 4 ( / 2) cn cn c n n c n n c n n T n T n n ≤ = − − = + ≤ + = + desired – residual whenever (c/2)n3 – n ≥ 0, for example, if c ≥ 2 and n ≥ 1. desired residual
Example(continued) We must also handle the initial conditions that is, ground the induction with base cases Base: I(n)=o(1) for all n<no, where no is a suitable constant For1≤n<mo, we have((1)≤cn3,ifwe pick c big enough This bound is not tight. Day 3 Introduction to Algorithms 2.5
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 < n0, where n0 is a suitable constant. • For 1 ≤ n < n0, we have “Θ(1)” ≤ cn3, if we pick c big enough. This bound is not tight!
a tighter upper bound? We shall prove that r(n)=o(n2) Assume that t(k)s ck for ko. lose Day 3 Introduction to Algorithms L2.6
Day 3 Introduction to Algorithms L2.6 A tighter upper bound? We shall prove that T(n) = O(n2). Assume that T(k) ≤ ck2 for k 0. Lose! [ desired – residual ]
A tighter upper bound! IDEA: Strengthen the inductive hypothesis Subtract a low-order term inductive hypothesis: T(k) 2 Pick c, b Day ig enough to handle the initial conditions Introduction to Algorithms 7
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) ≤ c1k2 – c2k for k 1. Pick c1 big enough to handle the initial conditions
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.8
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
Example of recursion tree Solve(m)=70n/4)+7(m/2)+n Day 3 Introduction to Algorithms L2.9
Day 3 Introduction to Algorithms L2.9 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2:
Example of recursion tree Solve(m)=70n/4)+7(m/2)+ 7(n) duction to algorith L2.10
Day 3 Introduction to Algorithms L2.10 Example of recursion tree T(n) Solve T(n) = T(n/4) + T(n/2) + n2: