text: # CSE 202 - Algorithms - PowerPoint PPT Presentation
  
  1 / 8
  
  Recurrences Master Method. CSE 202 - Algorithms. Your turn. For one of the following recursion trees ... T(n) = 3T(n/4) + 5n for n = 256, T(1)=5 T(n) = 2T(n/2) + 5n for n = 32, T(1)=5 T(n) = 3T(n/2) + 5n for n = 32, T(1)=5 T(n) = 3T(n/2) + n 2 for n = 32, T(1)=1
  
  I am the owner, or an agent authorized to act on behalf of the owner, of the copyrighted work described.
  
  CSE 202 - Algorithms
  
  Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author.While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.
  
  - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - -
  
  Recurrences
  
  Master Method
  
  ## CSE 202 - Algorithms
  
  CSE 202 - Recurrences
  
  For one of the following recursion trees ...
  
  • T(n) = 3T(n/4) + 5n for n = 256, T(1)=5
  
  • T(n) = 2T(n/2) + 5n for n = 32, T(1)=5
  
  • T(n) = 3T(n/2) + 5n for n = 32, T(1)=5
  
  • T(n) = 3T(n/2) + n2 for n = 32, T(1)=1
  
  • T(n) = 4T(n/2) + n2 for n = 32, T(1)=1
  
  ...figure out the total “conquer time” (the last term) needed at each level.
  
  Answer should be a sequence of 5 or 6 numbers.
  
  CSE 202 - Recurrences
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  ### Recursion Tree for T(n) = aT(n/b) + cn
  
  c n
  
  1 node at depth 0
  
  a nodes at depth 1
  
  c n/b
  
  c n/b
  
  c n/b
  
  ...
  
  a2 nodes at depth 2
  
  c n/b2
  
  c n/b2
  
  c n/b2
  
  c n/b2
  
  ...
  
  ...
  
  ...
  
  ...
  
  ...
  
  alogbn nodes at
  
  depth logb n
  
  T(n) = cn+ ac(n/b) + a2c(n/b2) + ... + alogbnc(n/ blogbn)
  
  = cn ( 1 + a/b + (a/b)2 + ... + (a/b)logbn ).
  
  CSE 202 - Recurrences
  
  ### How does your tree grow?
  
  What’s T(n) = cn ( 1 + a/b + (a/b)2 + ... + (a/b)logbn ) ?
  
  The largest term of a geometric series “dominates”.
  
  If a/b < 1, the first term dominates
  
  Thus, T(n)  (n).
  
  If a/b > 1, the last term dominates
  
  So T(n)  (n(a/b)logbn) = (n(a logbn/blogbn) ) = (n(a logbn/n) ) = (a logbn) = (nlogba).
  
  If a/b = 1, all terms are equal. There are logbn terms. So T(n)  (n logbn ) = (n lg n).
  
  CSE 202 - Recurrences
  
  ### Where are we ??
  
  In Divide & Conquer ... if T(n) = aT(n/b) + cn,
  
  (i.e. if you can combine pieces with linear work)
  
  then there are three cases:
  
  if a>b, then T(n) is (nlogba) (there are so many tiny subproblems, they dominate the time)
  
  if a=b, then T(n) is (n lg n) (just like merge sort)
  
  if a<b, then T(n) is (n) (big step is most expensive)
  
  CSE 202 - Recurrences
  
  ### What if combining takes f(n) work??
  
  In Divide & Conquer ... if T(n) = aT(n/b) + f(n), then three corresponding cases are:
  
  • The tiny subproblems dominate the run time
  
  • Happens when f(n) < c a f(n/b) for some c<1 and all n
  
  • If so, T(n)  (alogbn) = (nlogba).
  
  • All levels take about the same time
  
  • Happens when f(n) is (alogbn).
  
  • If so, T(n) = (f(n) lgn).
  
  • Big step is most expensive
  
  • Happens when f(n) > c a f(n/b) for some c>1 and all n.
  
  • If so, T(n) = (f(n)).
  
  CSE 202 - Recurrences
  
  ### Previous slide is “Master Method”
  
  Slight differences:
  
  Book’s condition on case 1, “f(n) is O(nlogba-)”, is slightly more general.
  
  It allows f(n) to be less uniform.
  
  Case 2 – remember alogbn = nlogba.
  
  Book has (unnecessary) extra condition in case 3
  
  “f(n) is (nlogba+)” is implied by “f(n) > c a f(n/b), c>1”
  
  Master method can “interpret n/b to mean either n/b or n/b”
  
  CSE 202 - Recurrences
  
  ### Other recurrences
  
  Master Method doesn’t always apply:
  
  What if, in MergeSort, we divided 75% - 25% ?
  
  T(n) = T(3n/4) + T(n/4) + c n.
  
  Or we divided into 1000 and n-1000 sized pieces?
  
  T(n) = T(1000) + T(n-1000) + cn (for n>1000).
  
  Or consider:
  
  T(n) = 2T(n/2) + n lg n.
  
  CSE 202 - Recurrences
explanation: The document is a PowerPoint presentation slide from a course on algorithms, specifically focusing on the topic of recurrences and the Master Method. It includes a math question asking the reader to figure out the total "conquer time" for given recursion trees, and it provides an answer that should be a sequence of 5 or 6 numbers.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # CSE 202 - Algorithms - PowerPoint PPT Presentation
  
  1 / 8
  
  Recurrences Master Method. CSE 202 - Algorithms. Your turn. For one of the following recursion trees ... T(n) = 3T(n/4) + 5n for n = 256, T(1)=5 T(n) = 2T(n/2) + 5n for n = 32, T(1)=5 T(n) = 3T(n/2) + 5n for n = 32, T(1)=5 T(n) = 3T(n/2) + n 2 for n = 32, T(1)=1
  
  I am the owner, or an agent authorized to act on behalf of the owner, of the copyrighted work described.
  
  CSE 202 - Algorithms
  
  Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author.While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.
  
  - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - -
  
  Recurrences
  
  Master Method
  
  ## CSE 202 - Algorithms
  
  CSE 202 - Recurrences
  
  For one of the following recursion trees ...
  
  • T(n) = 3T(n/4) + 5n for n = 256, T(1)=5
  
  • T(n) = 2T(n/2) + 5n for n = 32, T(1)=5
  
  • T(n) = 3T(n/2) + 5n for n = 32, T(1)=5
  
  • T(n) = 3T(n/2) + n2 for n = 32, T(1)=1
  
  • T(n) = 4T(n/2) + n2 for n = 32, T(1)=1
  
  ...figure out the total “conquer time” (the last term) needed at each level.
  
  Answer should be a sequence of 5 or 6 numbers.
  
  CSE 202 - Recurrences
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  c
  
  ### Recursion Tree for T(n) = aT(n/b) + cn
  
  c n
  
  1 node at depth 0
  
  a nodes at depth 1
  
  c n/b
  
  c n/b
  
  c n/b
  
  ...
  
  a2 nodes at depth 2
  
  c n/b2
  
  c n/b2
  
  c n/b2
  
  c n/b2
  
  ...
  
  ...
  
  ...
  
  ...
  
  ...
  
  alogbn nodes at
  
  depth logb n
  
  T(n) = cn+ ac(n/b) + a2c(n/b2) + ... + alogbnc(n/ blogbn)
  
  = cn ( 1 + a/b + (a/b)2 + ... + (a/b)logbn ).
  
  CSE 202 - Recurrences
  
  ### How does your tree grow?
  
  What’s T(n) = cn ( 1 + a/b + (a/b)2 + ... + (a/b)logbn ) ?
  
  The largest term of a geometric series “dominates”.
  
  If a/b < 1, the first term dominates
  
  Thus, T(n)  (n).
  
  If a/b > 1, the last term dominates
  
  So T(n)  (n(a/b)logbn) = (n(a logbn/blogbn) ) = (n(a logbn/n) ) = (a logbn) = (nlogba).
  
  If a/b = 1, all terms are equal. There are logbn terms. So T(n)  (n logbn ) = (n lg n).
  
  CSE 202 - Recurrences
  
  ### Where are we ??
  
  In Divide & Conquer ... if T(n) = aT(n/b) + cn,
  
  (i.e. if you can combine pieces with linear work)
  
  then there are three cases:
  
  if a>b, then T(n) is (nlogba) (there are so many tiny subproblems, they dominate the time)
  
  if a=b, then T(n) is (n lg n) (just like merge sort)
  
  if a<b, then T(n) is (n) (big step is most expensive)
  
  CSE 202 - Recurrences
  
  ### What if combining takes f(n) work??
  
  In Divide & Conquer ... if T(n) = aT(n/b) + f(n), then three corresponding cases are:
  
  • The tiny subproblems dominate the run time
  
  • Happens when f(n) < c a f(n/b) for some c<1 and all n
  
  • If so, T(n)  (alogbn) = (nlogba).
  
  • All levels take about the same time
  
  • Happens when f(n) is (alogbn).
  
  • If so, T(n) = (f(n) lgn).
  
  • Big step is most expensive
  
  • Happens when f(n) > c a f(n/b) for some c>1 and all n.
  
  • If so, T(n) = (f(n)).
  
  CSE 202 - Recurrences
  
  ### Previous slide is “Master Method”
  
  Slight differences:
  
  Book’s condition on case 1, “f(n) is O(nlogba-)”, is slightly more general.
  
  It allows f(n) to be less uniform.
  
  Case 2 – remember alogbn = nlogba.
  
  Book has (unnecessary) extra condition in case 3
  
  “f(n) is (nlogba+)” is implied by “f(n) > c a f(n/b), c>1”
  
  Master method can “interpret n/b to mean either n/b or n/b”
  
  CSE 202 - Recurrences
  
  ### Other recurrences
  
  Master Method doesn’t always apply:
  
  What if, in MergeSort, we divided 75% - 25% ?
  
  T(n) = T(3n/4) + T(n/4) + c n.
  
  Or we divided into 1000 and n-1000 sized pieces?
  
  T(n) = T(1000) + T(n-1000) + cn (for n>1000).
  
  Or consider:
  
  T(n) = 2T(n/2) + n lg n.
  
  CSE 202 - Recurrences
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a PowerPoint presentation slide from a course on algorithms, specifically focusing on the topic of recurrences and the Master Method. It includes a math question asking the reader to figure out the total "conquer time" for given recursion trees, and it provides an answer that should be a sequence of 5 or 6 numbers.
  
  Label: question-and-answer