Advanced Master Theorem สำหรับ Divide-and-Conquer Recurrences

Master Theorem แบบขยายสำหรับ recurrence แบบ T(n) = aT(n/b) + Θ(nᵏ logᵖ n)

เงื่อนไข

• a ≥ 1 (จำนวน subproblems)
• b > 1 (ขนาด subproblem)
• k ≥ 0, p เป็นจำนวนจริง

กรณีต่างๆ

1. a > bᵏ: T(n) = Θ(n^{log_b a})
2. a = bᵏ:
   • p > -1: T(n) = Θ(n^{log_b a} log^{p+1} n)
   • p = -1: T(n) = Θ(n^{log_b a} log log n)
   • p < -1: T(n) = Θ(n^{log_b a})
3. a < bᵏ:
   • p ≥ 0: T(n) = Θ(nᵏ logᵖ n)
   • p < 0: T(n) = Θ(nᵏ)

ตัวอย่าง

• Binary Search: T(n) = T(n/2) + Θ(1) → Θ(log n)
• Merge Sort: T(n) = 2T(n/2) + Θ(n) → Θ(n log n)