Unpacking the Master Theorem: Understanding its Proof and Cases

1 reply · 2K views · last reply
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Attachments
  • Screenshot of a textbook page titled Generic form, stating the master theorem for recurrences T(n) = a T(n/b) + f(n) with a ≥ 1, b > 1, and listing the meaning of n, a, n/b and f(n).
    beg.PNG
    15.9 KB · Views: 143
  • Case 1 of the Master Theorem: if f(n) = O(n^(log_b(a) - ε)) for some constant ε > 0 (using Big O notation), then T(n) = Θ(n^(log_b a)).
    case1.PNG
    5.2 KB · Views: 137
  • Text image of Case 2 of the Master Theorem: if f(n) = Θ(n^(log_b a) log^k n) for some constant k ≥ 0, then T(n) = Θ(n^(log_b a) log^(k+1) n).
    case2.PNG
    5.6 KB · Views: 120
  • Case 3 of the Master Theorem in generic form: if f(n) = Ω(n^(log_b(a)+ε)) for some constant ε > 0, and af(n/b) ≤ cf(n) for some constant c < 1 and sufficiently large n, then T(n) = Θ(f(n)).
    case3.PNG
    7.6 KB · Views: 137
Last edited:
Now I found the following proof:

View attachment 4435

Don't we have to explain further which case correponds to which of the following cases

  • The first term is dominant.
  • Each part of the summation is equally dominant.
  • The summation is a geometric series

and justify why it is like that? (Thinking)
 
Attachments
  • Slide titled Using iterative substitution deriving T(n) = aT(n/b) + f(n) by repeated expansion, ending in n^(log_b a) T(1) + sum from i=0 to (log_b n)-1 of a^i f(n/b^i), then listing three cases: first term dominant, each summation part equally dominant, summation is a geometric series.
    proof11.PNG
    9.3 KB · Views: 143