Master theorem Flashcards
(19 cards)
What type of recurrence does the Master Theorem apply to?
T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is a function.
What is the Master Theorem used for?
Solving recurrence relations from divide-and-conquer algorithms.
What is c in the Master Theorem?
c = log_b a — the work from the recursive structure.
What is Case 1 of the Master Theorem?
If f(n) = O(n^{c - ε}), then T(n) = Θ(n^c).
What is Case 2 of the Master Theorem?
If f(n) = Θ(n^c), then T(n) = Θ(n^c log n).
What is Case 3 of the Master Theorem?
If f(n) = Ω(n^{c + ε}) and the regularity condition holds, then T(n) = Θ(f(n)).
What is the regularity condition for Case 3?
There exists k < 1 such that for large n, a·f(n/b) ≤ k·f(n).
Does the Master Theorem apply if f(n) = n log n and c = 1?
No — n log n is not polynomially larger than n, so it doesn’t fit any case.
Does the Master Theorem apply to T(n) = T(n-1) + n?
No — the recurrence must divide input size, not subtract.
Can the Master Theorem handle floor or ceiling in n/b?
Yes — rounding doesn’t affect the result asymptotically.
What is the recurrence for MergeSort?
T(n) = 2T(n/2) + n
Which case of the Master Theorem does MergeSort fall under?
Case 2 — since f(n) = Θ(n) and c = log₂2 = 1.
What is the result of solving MergeSort using the Master Theorem?
T(n) = Θ(n log n)
Why does MergeSort achieve optimal performance among comparison-based sorts?
Because it meets the lower bound of Ω(n log n).
What is a caveat of the Master Theorem regarding f(n)?
It must grow polynomially faster or slower than n^c — not just slightly faster like n log n.
Why can’t we use the Master Theorem for all divide-and-conquer algorithms?
Some recurrences don’t match the required form or violate the conditions.
What does the Master Theorem compare?
The cost of combining subproblems f(n) vs. recursive cost n^log_b a.
What happens if f(n) grows slower than n^c?
Case 1 applies — T(n) = Θ(n^c).
What happens if f(n) grows faster than n^c and the regularity condition holds?
Case 3 applies — T(n) = Θ(f(n)).
