Solving Recurrences and Master Theorem in Algorithm Analysis

design and analysis of algorithms n.w
1 / 54
Embed
Share

Dive into the world of algorithm analysis with a focus on solving recurrences and mastering the theorem. Learn about asymptotic analysis, merge sort examples, and recurrence equations in this comprehensive guide. Explore how to analyze the running time of algorithms and gain insights into optimizing efficiency.

  • Algorithm Analysis
  • Recurrences
  • Master Theorem
  • Merge Sort
  • Asymptotic Analysis

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.

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. Design and Analysis of Algorithms L2: Solving Recurrences and Master Theorem Diptarka Chakraborty Steven Halim Sanjay Jain

  2. Design and Analysis of Algorithms Design and Analysis of Algorithms Last week: We studied about algorithms and asymptotics. Asymptotic analysis (to express running time as a function of input size)

  3. Analyzing running time of an algorithm Analyzing running time of an algorithm 1. We first consider recursive algorithms. 2. First step: Find some recurrence relation for time (dependent on input size). 3. Second step: Solve the recurrence

  4. Example: Merge Sort Example: Merge Sort MergeSort (?,?,?) 1. If ? = ?, then Done. 2. Let ? = ?+? 2 3. MergeSort(?,?,?) 4. MergeSort(?,? + 1,?) 5. Merge (?,?,?,?)

  5. Merge(?,?,?,?) ?1= ?; ?2= ? + 1; ?3= ? While ?1 ? and ?2 ? If ? ?1 ?[?2], then ? ?3 = ? ?1; ?1= ?1+ 1 Else ? ?3 = ? ?2; ?2= ?2+ 1 Endif ?3= ?3+ 1 Endwhile While ?1 ? ?[?3] = ?[?1]; ?1= ?1+ 1;?3= ?3+ 1 Endwhile While ?2 ?: ? ?3 = ? ?2; ?2= ?2+ 1; ?3= ?3+ 1 Endwhile For ? = ? ?? ?: ?[?] = ?[?] Endfor End

  6. Example: Merge Sort Example: Merge Sort MergeSort (?,?,?) the length of the list 1. If ? = ?, then Done Needs 1 time 2. Let ? = ?+? 2 Needs 1 time 3. MergeSort(?,?,?) Needs ?( ?(?) where ? = ? ? + 1, ? 2) time ? 2 time 4. MergeSort(?,? + 1,?) Needs ? 5. Merge (?,?,?,?) Needs ? time

  7. Recurrence equation for Recurrence equation for MergeSort MergeSort (1) ? 2 ?? ? = 1 ? ? = 2? + (?) ?? ? > 1 ? 2, ? 2 by ? Approximated asymptotically as we could have assumed ? to be a power of 2 (thus bounding the time required by the next higher power of 2). We will often do slight sloppiness as above, when it does not matter in the asymptotics, except for the constant factor. Base case: Often it is taken as a constant for small (constant) size input . 2. This is slightly sloppy, but does not matter

  8. Solving recurrence equations Solving recurrence equations Though not always easy, one can usually come up with recurrence equations by looking at the algorithm. Sometimes it needs some smartness/art to come up with right recurrence equation which we know how to solve. In this lecture we concentrate on how to solve recurrence equations.

  9. Solving recurrence equations: Solving recurrence equations: Some techniques Some techniques Telescoping method Recursion tree Master method Substitution method

  10. Telescoping method Telescoping method

  11. Telescoping Method Telescoping Method Consider any sequence ?0,?1,?2, ,?? Suppose we need to find ?=0 ?0 ?1) + (?1 ?2 + ?2 ?3 + + ?? 1 ?? Except for ?0in the beginning and ?? at the end, all other ?? the sum So the sum would be ?0 ?? Starting with 0 and ending with ?, may change based on usage ? 1(?? ??+1) appear exactly once as positive and once as negative in

  12. Telescoping series Telescoping series Example ?=1 ? ?+1 1 ? 1 ? ?+1 = 1 1 1 ? ?+1 1 ? 1 (1 1 ? 1 Thus, ?=1 1 1 1 ?1= 1,?2= 2, ,??= ? Sum is: 1 1 ? ?+1= ?=1 1 2 1 ? ?+1) ? 1 1 1 = 2+ 3+ . ? ?

  13. Telescoping Method Telescoping Method Often, main issue is now to try to convert equation we have into the form similar to ?=0 Consider merge sort, taking the constant in ?? 1 ? ? = 2? ? 1(?? ??+1) ? 2 + ? This can be written as (after dividing both sides by ?). ? 2 ? 2 ? 2 ? ? ? ? + 1, or ? ? = = 1 ? 2 ? ?

  14. Telescoping Method Telescoping Method Consider ??=? 2? Let ? = log? . Then, ?=0 2?. Then, ?? ?? 1= 1 ? 1 (??+1 ??) = ? So ?? ?0= ?. That is, T 2t So ? 2?= 2? (? + ?????). So ?(?) = ?(? log ?) 2t ? 20 = ? 20

  15. Other recurrences using Telescoping Method Other recurrences using Telescoping Method ? ? ? ? = ?? What should we divide both sides by? Aim is to express as ? ? + ?(?) ? ? ? ? ? ?(?)= + (?), for some ?, ? ? ? ? ? ? Which will give ? ? ?(?) = (?) ? And then do summation as in Telescoping method (need to sum up ? , which may not always be easy)

  16. Recursion tree Recursion tree Also see https://visualgo.net/en/recursion

  17. Recursion Tree Method Recursion Tree Method ? 2+ ?? (? > 0, is a constant) ? 4+?? 2 + ?? = 4? ? 8+?? 4 + 2??= 8T(n/8)+3cn ? ? = 2 ? ? 4+ 2?? = 2 2? = 4 2? .. = 2?? When ? = log?, (assume ? to be power of 2), it becomes ?? 1 + (?log?) = (?log?) Above looks like a tree , see next few slides. ? 2?+ ???

  18. Recursion tree: Recursion tree: Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. T(n) Use this custom code at https://visualgo.net/en/recursion for a visualization of this recursion tree if (n == 1) /* base case */ return 1; else /* recursive caseS */ return f(n/2) + f(n/2);

  19. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn T(n/2) T(n/2)

  20. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/2 cn/2 T(n/4) T(n/4) T(n/4) T(n/4)

  21. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/2 cn/2 cn/4 cn/4 cn/4 cn/4 (1)

  22. Recursion Recursion tree tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/2 cn/2 h = log n cn/4 cn/4 cn/4 cn/4 (1)

  23. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn cn/2 cn/2 h = log n cn/4 cn/4 cn/4 cn/4 (1)

  24. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn cn/2 cn cn/2 h = log n cn/4 cn/4 cn/4 cn/4 (1)

  25. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn cn/2 cn cn/2 h = log n cn/4 cn/4 cn cn/4 cn/4 (1)

  26. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn cn/2 cn cn/2 h = log n cn/4 cn/4 cn cn/4 cn/4 (1) (n) Number of leaves = n

  27. Recursion tree Recursion tree Solve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn cn/2 cn cn/2 h = log n cn/4 cn/4 cn cn/4 cn/4 (1) (n) Number of leaves = n Total = (n log n)

  28. Question 1 Note, C (UPPER CASE) is different from c (lower case)

  29. Answer of Question 1 T(n) = T(n-a) + T(a) + cn Answer: T(n) Cn2/a cn c(n-a) T(a) c(n-2a) T(a) height =n/a Ideally, it should be ?(?). For simplicity, assume ? ? ?? 2ac T(a) ac T(a)

  30. Answer of Question 1 T(n) = T(n-a) + T(a) + cn Recursion tree height is n/a At depth k, computation: T(a) + c(n-ka). Summed over height, we get: Arithmetic Series

  31. Question 2

  32. Answer Donald Knuth Turing Award winner Author of The Art of Computer Programming Has been called father of analysis of algorithms . Popularized asymptotic notation. Creator of TeX typesetting system.

  33. Announcement Announcement Written Assignment 1 will be uploaded in Canvas tomorrow afternoon All the instructions will be provided then

  34. Master Theorem/Method Master Theorem/Method

  35. The master theorem The master theorem Consider recurrence equations of the type: ? ? ? ? = ? ? + ? ? If ?,?,?(?) have a nice relation, then the master theorem applies Here we will always require ? 1,? > 1 are constants ?(?) is assumed to be positive except maybe for small values of ?

  36. The master theorem The master theorem Consider recurrence equations of the type: ? ? ? ? = ? ? + ? ? Let ? = log??,? > 0 and ? 0. Note: ??= ? Case 1: ? ? ? ?? ?: ? ? (??) Case 2: ? ? ??log?? : ? ? (??log?+1?) Case 3: ? ? ??+?: ? ? ? ? assuming that ?? ? ?? ? for all ? and some const c<1 (regularity condition) ?

  37. Examples: Examples: ? 3 + ?1.5 ? ? = 9 ? ? = log39 = 2 Case 1 applies ? ? ?2

  38. Examples: Examples: ? 3 + 3?2 ? ? = 9 ? ? = log39 = 2 Case 2 applies ? ? ?2log?

  39. T(n) = a T(n/b) + f (n) Proof Idea: Proof Idea: Recursion tree: f(n) ? ?(? ?2 ?(? f(n) a branches f(n/b) ?) f(n/b) f(n/b) a branches log?? ?2) f(n/b2) f(n/b2) f(n/b2) ?log???(1) (1) Number of leaves = ?log?? Note: ?log??= ?log??.

  40. Proof: Proof: Cost at the leaves: (?log??) = ?log??= (??) log?? 1???(? Cost at the other levels: ?=0 Now depends on which of the above two costs dominates , we get the three cases Will be shown visually with examples in a separate video by Steven ??)

  41. Proof: Proof: Case 1: ? ? ?(?? ?) Suppose ? ? ??? ?. ? ? ? ? ?? ? ?? (log??) 1 ?? ? ?? (log??) ? ?? ? ?? ??? = ?(?? ? ??? )=c(?? ? ???) ?? ?=0 b? 1 (using the formula for GP sum) ?? 1 ??) ??? ??? log?? 1???(? ? ?? Thus, ?=0 ?? 1

  42. Proof: Proof: Case 3: ? ? (??+?) Then, clearly leaf cost is small compared to the cost at other levels (even at the root). Using the regularity condition that ?? ? ? ?? 1 ??? ? ?? ? , ? ?? ? ?? 1? ? Cost of level ? ??: ??? Total cost of all the levels (except leave) is: ?=0 Note that regularity condition guarantees that each level cost decreases by constant factor As leaf cost is subsumed by other levels, we are done. log?? ??? ? = ? ? as ? < 1

  43. Proof: Proof: Case 2: ? ? (?? log??) , for some ? 0 ? ?? (????? ??(log?? log???)) Cost of level ? ??: ??? Note: log? is more than double log?? , for at least half the levels log?? 2is about ? Total cost of all the levels (except at leaves) is: ??log?? ????? = (??log?+1?) As leaf cost is subsumed by costs at other levels, we are done. as ?

  44. Question 3 Question 3 SolveT(n) = 4T(n/2) + n3 T(n) = (n2). T(n) = (n3). T(n) = (?log?). T(n) = (n2log?). 1. 2. 3. 4.

  45. Answer of Question 3 Answer of Question 3 T(n) = 4T(n/2) + n3 a = 4, b = 2 nlogba = n2; f(n) = n3. CASE 3: f(n) = (n2+ ) for = 1 and 4(n/2)3 cn3 (reg. cond.) for c = 1/2. T(n) = (n3).

  46. Can we always use master method? Can we always use master method? ?3 T(?) = 8?(? 2) + log ? ? = 8,? = 2,? = 2 None of the cases apply

  47. Substitution method Substitution method

  48. Substitution Method Substitution Method Guess and answer and verify (usually by induction)

  49. Subsitution Subsitution Method Method ? 2 + ?1.5 Example: ? ? = 8? Assume ? 1 = ?1for some constant ?1 Guess ? ? ?2?5, for ? ?0some constant ?2, ?0 Set ?2= max(2,?1+ 1) and ?0= 1 Base case: ? = 1, equation holds as ?1 ?2 15 Assume by induction that it holds, for all ? ? Then for ? = ? + 1, by induction, ? 2+ ?1.5 8?2 Thus, ? ? ?2?5= ? ?5 5 + ?1.5 ?2?5 ? 2 + ?1.5 ?2?5 ? ? = 8? 4

  50. Subsitution Subsitution Method Method We may not get tight bounds, as we may overguess the bound as in previous slide. Can we guess ? ? ?(?3) and try to prove it by induction?

More Related Content