ในการวิเคราะห์อัลกอริทึม พบ Recurrence Relations (สมการประกอบ) ที่ใช้ฟังก์ชันเดียวกันในนิพจน์ พบบ่อยใน Recursive Algorithms และ Divide & Conquer
ตัวอย่าง 1: Binary Search
ตรวจสอบกลาง ถ้าตรงจบ ไม่งั้นไป Left/Right Subarray ขนาดลด n/2 สมมติ T(n) เวลาทำงาน Base Case O(1)
$$T(n) = \begin{cases} T(1) & \text{for } n \leq 1 \\ T(\lfloor \frac{n}{2} \rfloor) + c & \text{for } n > 1 \end{cases}$$
ตัวอย่าง 2: Merge Sort
แบ่ง List 2 ส่วน จน Size=1 แล้ว Merge เรียง Merge ใช้ O(n)
$$T(n) = \begin{cases} T(1) & \text{for } n = 1 \\ 2T(\frac{n}{2}) + cn & \text{for } n > 1 \end{cases}$$
แก้สมการเหล่านี้ได้หลายวิธี: Substitution Method, Recurrence Tree Method, Master Theorem (สำหรับรูปแบบพิเศษ)
