Methods for Solving Recurrence Relations: Substitution, Iteration, Recursion Tree
Explore different methodologies for solving recurrence relations such as the substitution method, iteration method, and recursion tree. Dive into examples and understand how to apply these methods effectively in algorithm analysis.
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
CMPE371 Analysis of Algorithms FALL 2023-2024 Lecture 4 Part IV
Methods for Solving Recurrences Substitution method Iteration method Recursion tree method Master method
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: T(n)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 T(n/2) T(n/4)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 (n/2)2 (n/4)2 T(n/8) T(n/4) T(n/16) T(n/8)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 (n/2)2 (n/4)2 (n/8)2 (n/4)2 (n/16)2 (n/8)2 (1)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 2 n (n/2)2 (n/4)2 (n/8)2 (n/4)2 (n/16)2 (n/8)2 (1)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 2 n 5n 2 (n/2)2 (n/4)2 16 (n/8)2 (n/4)2 (n/16)2 (n/8)2 (1)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 2 n 5n 2 (n/2)2 (n/4)2 16 25n 2 (n/8)2 (n/4)2 (n/16)2 (n/8)2 256 (1)
Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 2 n 5n 2 (n/2)2 (n/4)2 16 25n 2 (n/8)2 (n/4)2 (n/16)2 (n/8)2 256 ) ( 1 ( ) 16 geometric series ( ) 16 (1) 2 3 2 5 5 5 + + + + n Total = 16 = (n2)
Example W(n) = 2W(n/2) + n2 Subproblem size at level i is: n/2i Subproblem size hits 1 when 1 = n/2i i = lgn Cost of the problem at level i = (n/2i)2 No. of nodes at level i = 2i i i 2 Total cost: lg = 1 lg = 1 n n 1 1 1 n = = + = + + = + = lg 2 2 2 2 n ( ) 2 ) 1 ( ( ) ( ) 2 W n W n n n O n n O n n 1 i 2 2 2 1 0 0 0 i i i 2 W(n) = O(n2)
Example E.g.: T(n) = 3T(n/4) + cn2 Subproblem size at level i is: n/4i Subproblem size hits 1 when 1 = n/4i i = log4n Cost of a node at level i = c(n/4i)2 Number of nodes at level i = 3i last level has 3log4n = nlog43nodes Total cost: ( 16 16 0 0 i i = = i i ) ( ) ( ) log 1 n 3 3 1 4 = + + = + = log 3 log 3 log 3 2 2 2 2 ( ) ( ) T n cn n cn n cn n O n 4 4 4 3 1 16 T(n) = O(n2)
Example W(n) = W(n/3) + W(2n/3) + n The longest path from the root to a leaf is: n (2/3)n (2/3)2n 1 Subproblem size hits 1 when 1 = (2/3)in i=log3/2n Cost of the problem at level i = n Total cost: ) 1 (log n 3/ 2 n n + + = + (log ) n ( ) ... 2 (1) W n n W 3/ 2 = 0 i log n lg 1 n 3/ 2 + = n O n + = + = n O n + log 2 1 log ( ) ( ) lg ( ) n n n n O n n 3/ 2 3/2 lg3/2 lg3/2 = 0 i W(n) = O(nlgn)
The master method The master method applies to recurrences of the form T(n) = aT(n/b) + f(n) , where a 1, b > 1, and f is asymptotically positive.
Three common cases Compare f(n) with nlogba: 1. f(n) = O(nlogba ) for some constant > 0. f(n) grows polynomially slower than nlogba (by an n factor). Solution: T(n) = (nlogba) .
Three common cases Compare f(n) with nlogba: 2. f(n) = (nlogba lgkn) for some constant k 0. f(n) and nlogbagrow at similar rates. Solution: T(n) = (nlogbalgk+1n) .
Three common cases (cont.) Compare f(n) with nlogba: 3. f(n) = (nlogba + ) for some constant > 0. f(n) grows polynomially faster than nlogba(by an n factor), and f(n) satisfies the regularity condition that af(n/b) cf(n) for some constant c < 1. Solution: T(n) = (f(n)) . L2.17
Examples Ex. T(n) = 4T(n/2) + n a = 4, b = 2 nlogba= n2; f(n) = n. CASE 1: f(n) = O(n2 ) for 0< < 1. T(n) = (n2). Ex. T(n) = 4T(n/2) + n2 a = 4, b = 2 nlogba= n2; f(n) = n2. CASE 2: f(n) = (n2lg0n), that is, k = 0. T(n) = (n2lgn). L2.18
Examples Ex. T(n) = 4T(n/2) + n3 a = 4, b = 2 nlogba= n2; f(n) = n3. CASE 3: f(n) = (n2 + ) for 0< < 1 and 4(n/2)3 cn3 (reg. cond.) for <= c <1 T(n) = (n3). L2.19
