Trong quá trình phân tích các thuật toán, chúng tôi tìm thấy một số quan hệ lặp lại. Các quan hệ lặp lại này về cơ bản đang sử dụng cùng một hàm trong biểu thức. Trong hầu hết các trường hợp để phân tích thuật toán đệ quy và thuật toán chia và thu chúng ta nhận được các quan hệ lặp lại.
Ở đây chúng ta sẽ thấy một ví dụ về phương trình tái diễn với sự trợ giúp của một số ví dụ. Giả sử chúng ta đang sử dụng kỹ thuật tìm kiếm nhị phân. Trong kỹ thuật này, chúng tôi kiểm tra xem phần tử có ở cuối hay không. Nếu điều đó xuất hiện ở giữa, thì thuật toán kết thúc, nếu không, chúng tôi lấy đi lặp lại một trong hai mảng con bên trái và bên phải từ mảng thực tế. Vì vậy trong mỗi bước kích thước của mảng giảm đi n / 2. Giả sử thuật toán tìm kiếm nhị phân mất T (n) lượng thời gian để thực thi. Điều kiện cơ sở mất O (1) lượng thời gian. Vì vậy, phương trình lặp lại sẽ giống như dưới đây -
$$ T (n) =\ begin {case} T (1) &for \:n \ leq 1 \\ T (| \ frac {n} {2} \ rvert) + c &for \:n> 1 \ kết thúc {case} $$
Tương tự, nếu chúng ta chọn một ví dụ khác như sắp xếp hợp nhất, thì trong trường hợp đó, chúng ta chia danh sách thành hai phần. Sự phân chia này diễn ra cho đến khi kích thước danh sách chỉ còn 1. Sau đó, chúng tôi hợp nhất chúng theo thứ tự đã sắp xếp. Thuật toán hợp nhất mất O (n) lượng thời gian. Vì vậy, nếu thuật toán sắp xếp hợp nhất đang chiếm T (n) lượng thời gian, thì bằng cách chia nó thành hai nửa và thực hiện cùng một nhiệm vụ cho mỗi người trong số họ, chúng sẽ mất T (n / 2), v.v. Vì vậy, mối quan hệ lặp lại sẽ như dưới đây -
$$ T (n) =\ begin {case} T (1) &for \:n =1 \\ 2T (\ frac {n} {2}) + cn &for \:n> 1 \ end {case} $$
Chúng tôi có thể giải các phương trình này bằng các phương pháp khác nhau, chẳng hạn như phương pháp thay thế, phương pháp cây lặp lại và một số loại quan hệ lặp lại đặc biệt có thể được giải bằng phương pháp Chính.