Xem cách dùng phương pháp thay thế để giải quan hệ truy hồi (recurrence relations). Lấy hai ví dụ để hiểu rõ hơn.
Giả sử dùng tìm kiếm nhị phân (binary search). Kiểm tra phần tử có ở giữa không. Nếu có thì dừng, nếu không lấy nửa trái hoặc phải của mảng. Mỗi bước kích thước mảng giảm n/2. Giả sử binary search mất T(n) thời gian. Điều kiện cơ sở O(1). Quan hệ truy hồi:
$$T(n)=\begin{cases}T(1) & for\: n \leq 1\\T(\frac{n}{2})+c & for\: n > 1\end{cases}$$
Giải: Thay thế công thức từng bước:
$$T(n)=T(\frac{n}{2})+c$$
Thay 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$$
Khi $\frac{n}{2^{k}} = 1 \Rightarrow 2^{k}=n \Rightarrow k=\log_2 n$
Độ phức tạp T(n) = Θ(log n)
Ví dụ khác: Merge sort. Chia danh sách thành hai phần cho đến khi kích thước 1. Sau đó gộp theo thứ tự. Gộp mất O(n). Quan hệ truy hồi:
$$T(n)=\begin{cases}T(1) & for\: n = 1\\2T(\frac{n}{2})+cn & for\: n > 1\end{cases}$$
Giải: Thay thế:
$$T(n)=2T(\frac{n}{2})+cn$$
$$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$$
Khi $\frac{n}{2^{k}}=1 \Rightarrow k=\log_2 n$. Vậy T(n) = nT(1) + cn log₂ n
Độ phức tạp: Θ(n log n)