Trong phân tích thuật toán, tìm thấy các quan hệ truy hồi. Đây là các quan hệ dùng cùng hàm trong biểu thức. Thường gặp trong phân tích thuật toán đệ quy và chia để trị.
Ví dụ quan hệ truy hồi bằng một số ví dụ. Giả sử dùng tìm kiếm nhị phân. Kiểm tra phần tử ở giữa. Nếu có thì dừng, không thì lấy nửa trái hoặc phải. Mỗi bước kích thước giảm n/2. Giả sử binary search mất T(n) thời gian. 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}$$
Tương tự, Merge sort: chia danh sách thành hai phần cho đến kích thước 1. Gộp theo thứ tự 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}$$
Có thể giải các phương trình này bằng các phương pháp khác nhau: thay thế (substitution), cây truy hồi (recurrence tree), và một số quan hệ đặc biệt bằng Master theorem.