วิธีใช้ Substitution Method แก้ Recurrence Relations ด้วย 2 ตัวอย่าง
ตัวอย่าง 1: Binary Search
Binary Search ตรวจสอบกลาง ถ้าตรงจบ ไม่งั้นไป Left/Right Subarray ขนาดลดลง n/2 ทุกขั้น สมมติ T(n) = เวลาทำงาน Base Case O(1)
สมการ Recurrence:
$$T(n) = \begin{cases} T(1) & \text{for } n \leq 1 \\ T(\frac{n}{2}) + c & \text{for } n > 1 \end{cases}$$
แก้ด้วยการแทนค่า (Substitution):
$$T(n) = T(\frac{n}{2}) + c$$
แทน T(n/2):
$$T(n) = (T(\frac{n}{4}) + c) + c = T(\frac{n}{4}) + 2c$$
$$T(n) = T(\frac{n}{8}) + 3c$$
$$T(n) = T(\frac{n}{2^k}) + kc$$
เมื่อ n/2ᵏ = 1 → 2ᵏ = n → k = log₂n
Complexity: T(n) = Θ(log n)
ตัวอย่าง 2: Merge Sort
แบ่ง List 2 ส่วน จน Size = 1 แล้ว Merge เรียงลำดับ Merge ใช้ O(n) สมการ Recurrence:
$$T(n) = \begin{cases} T(1) & \text{for } n = 1 \\ 2T(\frac{n}{2}) + cn & \text{for } n > 1 \end{cases}$$
แก้ด้วย Substitution:
$$T(n) = 2T(\frac{n}{2}) + cn$$
แทน T(n/2):
$$T(n) = 2(2T(\frac{n}{4}) + \frac{cn}{2}) + cn = 4T(\frac{n}{4}) + 2cn$$
$$T(n) = 8T(\frac{n}{8}) + 3cn$$
$$T(n) = 2^k T(\frac{n}{2^k}) + kcn$$
เมื่อ n/2ᵏ = 1 → k = log₂n
$$T(n) = nT(1) + cn \log_2 n$$
Complexity: Θ(n log n)
