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!