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.3Day 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