Solving Recurrence Relations Efficiently

more recurrences n.w
1 / 37
Embed
Share

Learn techniques for solving recurrence relations efficiently in this comprehensive guide. Explore key concepts such as substitution method, recursion-tree method, and master method to simplify complex recursive functions and optimize computational costs.

  • Recurrence relations
  • Master method
  • Substitution
  • Recursion-tree
  • Computational cost
rayaanacharya
yien_7 Follow

Uploaded on | 0 Views

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.

Download 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.

E N D

Presentation Transcript

  1. More Recurrences David Kauchak cs140 Spring 2024

  2. Administrative Group sessions Assignment 1

  3. Recurrence A function that is defined with respect to itself on smaller inputs = + ( ) 2 ( ) 2 / T n T n n = + ( ) 16 ( ) 4 / T n T n n = ) 1 + 2 ( ) 2 ( T n T n n

  4. The challenge Recurrences are often easy to define because they mimic the structure of the program But they do not directly express the computational cost, i.e. n, n2, We want to remove self-recurrence and find a more understandable form for the function

  5. Three approaches Substitution method: when you have a good guess of the solution, prove that it s correct Recursion-tree method: If you don t have a good guess, the recursion tree can help. Then solve with substitution method. Master method: Provides solutions for recurrences of the form: ( ) ( n aT n T = + / ) ( ) b f n

  6. Recursion Tree Guessing the answer can be difficult = = + + 2 ( ( ) ) 3 T ( ) 4 / ) 3 / T T n n T n n n 2 + ( 2 ( ) 3 / T n cn The recursion tree approach Draw out the cost of the tree at each level of recursion Sum up the cost of the levels of the tree Find the cost of each level with respect to the depth Figure out the depth of the tree Figure out (or bound) the number of leaves Verify your answer using the substitution method

  7. cost = + 2 ( ) 3 ( ) 4 / T n T n n cn2 cn2 T(n/4 ) T(n/4 ) T(n/4 )

  8. cost = + 2 ( ) 3 ( ) 4 / T n T n n cn2 cn2 3/16cn2 2 2 2 n n n 4 4 4 c c c n n n n n n n n n T T T T T T T T T 16 16 16 16 16 16 16 16 16

  9. cost = + 2 ( ) 3 ( ) 4 / T n T n n cn2 cn2 3/16cn2 2 2 2 n n n 4 4 4 c c c 2 2 2 2 2 2 2 n n 2 2 n n n n (3/16)2cn2 n n n 16 16 c c 16 16 16 16 c c c c 16 c 16 16 c c d 3 2 cn What is the cost at each level? 16

  10. What is the depth of the tree? At each level, the size of the data is divided by 4 n = 1 d 4 n = log 0 d 4 = d log log 4 0 n log = 4 log d n = log d n 4

  11. = + 2 ( ) 3 ( ) 4 / T n T n n cn2 2 2 2 n n n 4 4 4 c c c 2 2 2 2 2 2 2 n n 2 2 n n n n n n n 16 16 c c 16 16 16 16 c c c c 16 c 16 16 c c ) 1 ( T How many leaves are there?

  12. How many leaves? How many leaves are there in a complete ternary tree of depth d? 3 = log n d 3 4

  13. Total cost 2 1 d 3 3 3 = + + + + + log n 2 2 2 2 ( ) ... 3 ( ) T n cn cn cn cn 4 16 16 16 i log 1 n 3 4 = = 1 = + log n 2 3 ( ) cn 4 16 3 0 i i + log n 2 3 ( ) cn 4 1 16 = k x 0 i = 1 x 0 k = + log n 2 3 ( ) cn 4 let x = 3/16 / 3 ( 1 16 ) ? 16 = + log n 2 3 ( ) cn 4 13

  14. 16 Total cost = + log n 2 ( ) 3 ( ) T n cn 4 13 log n = 4 log log 3 n 3 4 4 4 = log log 3 n 4 4 4 Assignment 0! log 3 = 4 log n 4 4 = log4 3 n 16 = + log 3 2 ( ) ( ) T n cn n 4 13 = 2 ( ) ( ) T n O n

  15. Recursion tree If you went through the exact calculation (like we just did), you can be done! Often, this isn t feasible (or desirable) Instead, use the recursion tree to get a good guess

  16. Verify solution using substitution = + 2 ( ) 3 ( ) 4 / T n T n n Assume T(k) = O(k2) for all k < n Show that T(n) = O(n2) Given that T(n/4) = O((n/4)2), then there exists n positive n cg constants n c and such that n = ( ( )) ( : ) n O g n f 0 ( ) ( for ) all f n 0 T(n/4) c(n/4)2

  17. = + 2 ( ) 3 ( ) 4 / T n T n n To prove that Show that T(n) = O(n2) we need to identify the appropriate constants: ) ( 0 n f there exists positive n cg constants n c and such that n = ( ( )) ( : ) n O g n f ( for ) all n 0 i.e. some constant c such that T(n) cn2 = + 2 ( ) 3 ( ) 4 / T n T n n = + + 2) 4 / 16 / 3 2 3 cn ( c n n n 2 2 = ??2 ??213 residual 16+ ?2 a constant exists if ??213 16+ ?2 0

  18. = + 2 ( ) 3 ( ) 4 / T n T n n To prove that Show that T(n) = O(n2) we need to identify the appropriate constants: ) ( 0 n f there exists positive n cg constants n c and such that n = ( ( )) ( : ) n O g n f ( for ) all n 0 i.e. some constant c such that T(n) cn2 13 16+ ?2 0 13 16 ?2 ? 16 ??2 ??2 13

  19. Master Method Provides solutions to the recurrences of the form: ( ) ( n aT n T = + / ) ( ) b f n = = log log a a if ( ) ( for ) then , 0 ( ) ( ) f n O n T n n b b = = log log a a if ( ) ( then ), ( ) ( log ) f n n T n n n b b + = log a if ( ) ( for ) and 0 ( / ) ( for ) 1 f n n af n b cf n c b = then ( ) ( ( )) T n f n

  20. = + ( ) 16 ( ) 4 / T n T n n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 16 4 n a = b = f(n) = = nlog a log4 16 n b = 2 n = 2 is ( ? ) n O n Case 1: (n2) = 2 is ( ? ) + n n = 2 is ( ? ) n n

  21. = + n ( ) ( ) 2 / 2 T n T n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 1 2 2n a = b = f(n) = = nlog a log2 1 n b = 0 n Case 3? 2 is = 0 n 2 is ( ? ) O n / 2 n n 2 for 1 ? c c = 0 n 2 is ( ? ) + n = 0 n 2 is ( ? ) n

  22. = + n ( ) ( ) 2 / 2 T n T n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) / 2 n n 2 is 2 for 1 ? c c Let c = 1/2 / 2 n n 2 / 1 ( 2 ) 2 T(n) = (2n) / 2 1 n n 2 2 2 / 2 1 n n 2 2

  23. = + ( ) 2 ( ) 2 / T n T n n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 2 2 n a = b = f(n) = = nlog a log2 2 n b = 1 n = 1 is ( ? ) n O n Case 2: (n log n) = 1 is ( ? ) + n n = 1 is ( ? ) n n

  24. = + ( ) 16 ( ) 4 / ! T n T n n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 16 4 n! a = b = f(n) = = nlog a log4 16 n b = 2 n Case 3? 16 is (n/ = 2 is ! ( ? ) n O n 4 for 1 ? )! cn! c = 2 is ! ( ? ) + n n = 2 is ! ( ? ) n n

  25. = + ( ) 16 ( ) 4 / ! T n T n n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) is 16 4 for 1 ? (n/ )! cn! c Let c = 1/2 cn = ! / 1 (n 2 / ! )! 2 n T(n) = (n!) therefore, / 1 16 ( / 4 )! ( / 2 )! 2 ! n n n

  26. = + ( ) 2 ( ) 2 / log = and 0 T n T n n = = = T = log log a a if ( ) ( for ) then , 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 2 a = b = f(n) = = log 2 nlog a n b 2 2 logn / 1 2 2 = log n 2 = n = / 1 2 is log ( ? ) n O n Case 1: () n = / 1 2 is log ( ? ) + n n = / 1 2 is log ( ? ) n n

  27. = + ( ) 4 ( ) 2 / T n T n n = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) 4 2 n a = b = f(n) = = nlog a log2 4 n b = 2 n = 2 is ( ? ) n O n Case 1: (n2) = 2 is ( ? ) + n n = 2 is ( ? ) n n

  28. Recurrences = + = + ( ) 7 ( ) 7 / ( ) 2 ( ) 3 / T n T n n T n T n d = = = = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O n T n n b b log log a a if if ( ( ) ) ( n then ), for ) ( ) ( log ) ) ( f f n n n T n n ( n b b + log a ( / for ) 1 af n b cf n c b = then ( ) ( ( )) T n f n = ) 1 + ( ) ( log T n T n n = + 3 ( ) 8 ( ) 2 / T n T n n

  29. Why does the master method work? T = + ( ) ( / ) ( ) n aT n b f n (n ) (n ) f f a ( / ) af n b ( / ) ( / ) f n b f n b ( / ) f n b a a a 2 2 ( / ) a f n b 2 2 ( / ) f n b ( / ) 2 f n b 2 2 2 ( / ) f n b ( / ) ( / ) ( / ) f n b f n b f n b 2 2 2 ( / ) f n b ( / ) ( / ) f n b f n b

  30. What is the depth of the tree? At each level, the size of the data is divided by b n = 1 d b n = log 0 d b = b log log 4 0 n log = log d b n = log d n b

  31. How many leaves? How many leaves are there in a complete a-ary tree of depth d? = = log n d a a nlog b a b

  32. = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b Total cost log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) = + + + + + log 3 a 2 2 1 1 n n ( ) ( ) ( / ) ( / ) ... ( / ) ( ) T n cf n af n b a f n b a f n b n b log 1 a n b = + log a i i ( / ) ( ) f n b n b = 0 i Case 1: cost is dominated by the cost of the leaves log 1 a n b = log a i i ( / ) ( ) f n b n b = 0 i

  33. = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b Total cost log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) = + + + + + log 3 a 2 2 1 1 n n ( ) ( ) ( / ) ( / ) ... ( / ) ( ) T n cf n af n b a f n b a f n b n b log 1 a n b = + log a i i ( / ) ( ) f n b n b = 0 i Case 2: cost is evenly distributed across tree As we saw with mergesort, log n levels to the tree and at each level f(n) work

  34. = = = T = log log a a if ( ) ( for ) then , 0 = and 0 ( ) ( ) f n O ( n n T n n b b Total cost log log a a if ( ) ( ( ) then ), for ) ( n f ( ) ( log ) b ) f n ( n n = T n n n cf b b + log a if ) ( / ( for ) 1 f then n af n n c b ( )) T(n)=cf(n)+af(n/b)+a2f(n/b2)+...+ad-1f(n/bd-1)+Q(nlogba3) log 1 a n b = + log a i i ( / ) ( ) f n b n b = 0 i Case 3: cost is dominated by the cost of the root (n ) f a

  35. Other forms of the master method = + d ( ) ( / ) ( ) T n aT n b O n d ( ) if d log O n a b = = d ( ) ( log log ) if d log T n O n n a b a ( ) if d log O n a b b

  36. Changing variables n T ( = + ) 2 ( ) log T n n Guesses? We can do a variable change: let m = log2n (or n = 2m) = + / 2 m m 2 ( ) 2 2 ( ) T T m Now, let S(m)=T(2m) = + ( ) 2 ( ) 2 / S m S m m

  37. Changing variables S(m)=2S(m/2)+m Guess? = ( ) ( log ) S m O m m = = = m ( ) 2 ( T ) ( ) ( log ) T n S m O m m substituting m=log n = ( ) (log log log ) T n O n n

Related


No related presentations.

More Related Content