Solving Recurrences with Substitution Method
Explore the Substitution Method for solving recurrences in algorithms. Learn about guessing solutions, using induction for proof, and applying asymptotic notation. Examples like Binary Search are provided with step-by-step explanations. Dive into CS 477/677 Lecture 4 for in-depth knowledge.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Analysis of Algorithms CS 477/677 Instructor: Monica Nicolescu Lecture 4
Methods for Solving Recurrences Iteration method Substitution method Recursion tree method Master method CS 477/677 - Lecture 4 2
The substitution method 1. Guess a solution 2. Use induction to prove that the solution works CS 477/677 - Lecture 4 3
Substitution method Guess a solution T(n) = O(g(n)) Induction goal: apply the definition of the asymptotic notation T(n) d g(n), for some d > 0 and n n0 Induction hypothesis: T(k) d g(k) for all k < n Prove the induction goal Use the induction hypothesis to find some values of the constants d and n0 for which the induction goal holds CS 477/677 - Lecture 4 4
Example: Binary Search T(n) = c + T(n/2) Guess: T(n) = O(lgn) Induction goal: T(n) d lgn, for some d and n n0 Induction hypothesis: T(n/2) d lg(n/2) Proof of induction goal: T(n) = T(n/2) + c d lg(n/2) + c = d lgn d + c d lgn if: d + c 0, d c CS 477/677 - Lecture 4 5
Example: Binary Search T(n) = c + T(n/2) Boundary conditions: Base case: n0 = 1 T(1) = c has to verify condition: T(1) d lg 1 c d lg 1 = 0 contradiction Choose n0 = 2 T(2) = 2c has to verify condition: T(2) d lg 2 2c d lg 2 = d choose d 2c We can similarly prove that T(n) = ?(lgn) and therefore: T(n) = (lgn) CS 477/677 - Lecture 4 6
Example 2 T(n) = T(n-1) + n Guess: T(n) = O(n2) Induction goal: T(n) c n2, for some c and n n0 Induction hypothesis: T(n-1) c(n-1)2 Proof of induction goal: T(n) = T(n-1) + n c (n-1)2 + n = cn2 (2cn c - n) cn2 if: 2cn c n 0 c n/(2n-1) c 1/(2 1/n) For n 1 2 1/n 1 any c 1 will work CS 477/677 - Lecture 4 7
Example 2 T(n) = T(n-1) + n Boundary conditions: Base case: n0 = 1 T(1) = 1 has to verify condition: T(1) c (1)2 1 c OK! We can similarly prove that T(n) = ?(n2) and therefore: T(n) = (n2) CS 477/677 - Lecture 4 8
Example 3 T(n) = 2T(n/2) + n Guess: T(n) = O(nlgn) Induction goal: T(n) cn lgn, for some c and n n0 Induction hypothesis: T(n/2) cn/2 lg(n/2) Proof of induction goal: T(n) = 2T(n/2) + n 2c (n/2)lg(n/2) + n = cn lgn cn + n cn lgn if: - cn + n 0 c 1 CS 477/677 - Lecture 4 9
Example 3 T(n) = 2T(n/2) + n Boundary conditions: Base case: n0 = 1 T(1) = 1 has to verify condition: T(1) cn0lgn0 1 c * 1 * lg1 = 0 contradiction Choose n0 = 2 T(2) = 4 has to verify condition: T(2) c * 2 * lg2 4 2c choose c = 2 We can similarly prove that T(n) = ?(nlgn) and therefore: T(n) = ?(nlgn) CS 477/677 - Lecture 4 10
Changing variables T(n) = 2T( ) + lgn n Rename: m = lgn n = 2m T (2m) = 2T(2m/2) + m Rename: S(m) = T(2m) S(m) = 2S(m/2) + m S(m) = O(mlgm) (demonstrated before) T(n) = T(2m) = S(m) = O(mlgm)=O(lgnlglgn) Idea: transform the recurrence to one that you have seen before CS 477/677 - Lecture 4 11
Changing variables (cont.) T(n) = T(n/2) + 1 Rename: n = 2m (n/2 = 2m-1) T (2m) = T(2m-1) + 1 Rename: S(m) = T(2m) S(m) = S(m-1) + 1 = 1 + S(m-1) = 1 + 1 + S(m-2) = 1 + 1 + + 1 + S(1) m -1 times S(m) = O(m) T(n) = T(2m) = S(m) = O(m) = O(lgn) CS 477/677 - Lecture 4 12
The recursion-tree method Convert the recurrence into a tree: Each node represents the cost incurred at that level of recursion Sum up the costs of all levels Used to guess a solution for the recurrence CS 477/677 - Lecture 4 13
Readings Chapter 4 CS 477/677 - Lecture 4 14
