Analysis of AlgorithmsCS 477/677
Instructor: MonicaNicolescuLecture 4
CS 477/677 - Lecture 5
2
Methods for Solving Recurrences
Iteration methodSubstitution methodRecursion tree methodMaster method
CS 477/677 - Lecture 5
3
The substitution method
Guess a solutionUse induction to prove that the solution works
CS 477/677 - Lecture 5
4
Substitution method
Guess a solutionT(n) = O(g(n))Induction goal:apply the definition of the asymptotic notationT(n)≤d g(n), for somed > 0andn≥ n0Inductionhypothesis:T(k)≤d g(k) for all k < nProve the induction goalUse theinduction hypothesistofind some values of the constantsdandn0for which theinduction goalholds
CS 477/677 - Lecture 5
5
Example: Binary Search
T(n) = c + T(n/2)Guess:T(n) = O(lgn)Induction goal:T(n)≤d lgn, for somedandn≥ n0Inductionhypothesis:T(n/2)≤d lg(n/2)Proof of induction goal:T(n) = T(n/2) + c≤ dlg(n/2) + c= d lgn – d + c≤ d lgnif:– d + c ≤ 0, d ≥ c
CS 477/677 - Lecture 5
6
Example: Binary Search
T(n) = c + T(n/2)Boundary conditions:Base case:n0= 1⇒T(1) = chas to verify condition:T(1) ≤ dlg1⇒c ≤ dlg1 = 0– contradictionChoosen0= 2⇒T(2) = 2chas to verify condition:T(2) ≤ dlg2⇒2c ≤ dlg2 = d⇒choosed≥ 2cWe can similarly prove thatT(n) =𝝮(lgn)and therefore:T(n) =Θ(lgn)
CS 477/677 - Lecture 5
7
Example 2
T(n) = T(n-1) + nGuess:T(n) = O(n2)Induction goal:T(n)≤c n2, for somecandn≥ n0Inductionhypothesis:T(n-1)≤c(n-1)2Proof of induction goal:T(n) = T(n-1) + n≤ c(n-1)2+ n= cn2– (2cn – c - n)≤ cn2if: 2cn – c – n ≥ 0⇒ c≥ n/(2n-1)⇒ c≥ 1/(2 – 1/n)For n≥ 1⇒2 – 1/n ≥ 1⇒anyc ≥ 1will work
CS 477/677 - Lecture 5
8
Example 2
T(n) = T(n-1) + nBoundary conditions:Base case:n0= 1⇒T(1) = 1has to verify condition:T(1)≤ c (1)2⇒1 ≤ c⇒OK!We can similarly prove thatT(n) =𝝮(n2)and therefore:T(n) =Θ(n2)
CS 477/677 - Lecture 5
9
Example 3
T(n) = 2T(n/2) + nGuess:T(n) = O(nlgn)Induction goal:T(n)≤cnlgn, for somecandn≥ n0Inductionhypothesis:T(n/2)≤cn/2lg(n/2)Proof of induction goal:T(n) = 2T(n/2) + n≤ 2c (n/2)lg(n/2) + n=cnlgn–cn+ n≤cnlgnif: -cn+ n ≤ 0⇒c≥ 1
CS 477/677 - Lecture 5
10
Example 3
T(n) = 2T(n/2) + nBoundary conditions:Base case:n0= 1⇒T(1) = 1has to verify condition:T(1) ≤ cn0lgn0⇒1 ≤ c * 1 * lg1 = 0– contradictionChoose n0= 2⇒T(2) = 4has to verify condition:T(2) ≤ c * 2 * lg2⇒4 ≤ 2c⇒choose c = 2We can similarly prove thatT(n) =𝝮(nlgn)and therefore:T(n) = 𝝮(nlgn)
CS 477/677 - Lecture 5
11
Changing variables
Rename:m =lgn⇒ n = 2mT (2m) = 2T(2m/2) + mRename: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
T(n) = 2T( ) + lgn
CS 477/677 - Lecture 5
12
Changing variables (cont.)
Rename:n = 2m(n/2 = 2m-1)T(2m) = T(2m-1) + 1Rename:S(m) = T(2m)S(m) = S(m-1) + 1= 1 + S(m-1) = 1 + 1 + S(m-2) = 1 + 1 + …+ 1 + S(1)S(m) = O(m)⇒T(n) = T(2m) = S(m) = O(m) = O(lgn)
T(n) = T(n/2) + 1
m -1 times
CS 477/677 - Lecture 5
13
The recursion-tree method
Convert the recurrence into a tree:Each node represents the cost incurred at that level of recursionSum up the costs of all levels
Used to “guess” a solution for the recurrence
CS 477/677 - Lecture 5
14
Readings
Chapter 4
0
Embed
Upload