Master Theorem for Dividing Functions

General Form

• Recurrence relation: $T(n) = aT\left(\frac{n}{b}\right) + f(n)$
• Assumptions:
  • $a \geq 1$
  • $b > 1$
  • $f(n) = \Theta(n^k (\log n)^p)$
• Key values:
  • $\log_b a$
  • $k$ (power of $n$)

Cases

Case 1: $

log_b a > k$

• Solution: $\Theta(n^{\log_b a})$
• Example:
  • $T(n) = 2T\left(\frac{n}{2}\right) + 1$
  • $a = 2$, $b = 2$
  • $f(n) = \Theta(1) = n^0 \log n^0$
  • $ log_2 2 = 1, k = 0$, so $\Theta(n^1) = \Theta(n)$

Case 2: $

log_b a = k$

• Subcases:
  1. If $p > -1$, Solution: $\Theta(n^k (\log n)^{p+1})$
  2. If $p = -1$, Solution: $\Theta(n^k \log(\log n))$
  3. If $p < -1$, Solution: $\Theta(n^k)$
• Example:
  • $T(n) = 2T\left(\frac{n}{2}\right) + n$
    • $ log_2 2 = 1, k = 1$ so $f(n) = n$
    • $p = 0$, thus $\Theta(n \log n)$
  • $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$
    • $ log_2 2 = 1, k = 1$
    • $p = -1$, thus $\Theta(n \log (\log n))$

Case 3: $

log_b a < k$

• Subcases:
  1. If $p \geq 0$, Solution: $\Theta(n^k (\log n)^p)$
  2. If $p < 0$, Solution: $\Theta(n^k)$
• Example:
  • $T(n) = T\left(\frac{n}{2}\right) + n^2$
    • $ log_1 2 < 2$, $k = 2$, no log term
    • Solution: $\Theta(n^2)$
  • $T(n) = 2T\left(\frac{n}{2}\right) + n^3$
    • $ log_2 2 = 1$, $k = 3$ (greater)
    • Solution: $\Theta(n^3)$

Summary of Applications

• Use $\log_b a$ and $k$ to determine the case.
• Apply the appropriate solution based on comparisons.
• Examples illustrate how to extract values and find solutions.