Định lý tổng quát (Master theorem) tính độ phức tạp các thuật toán chia để trị

Các thuật toán chia để trị thường chuyển bài toán lớn về các bài toán nhỏ rồi kết hợp lời giải các bài toán nhỏ để tạo ra kết quả của bài toán ban đầu. Để tính độ phức tạp của các thuật toán chia để trị, người ta thường sử dụng định lý tổng quát sau.

Định lý (Master theorem): Cho , ta có

1. Nếu với thì .
2. Nếu với thì .
3. Nếu thì .

Nhận xét: Có thể hiểu là ta chia bài toán lớn ra thành bài toán có kích thước để giải rồi dùng phép tính để kết hợp lời giải các bài toán con lại.

Chứng minh:

Giả sử (không mất tính tổng quát do ta có thể chọn nhỏ nhất sao cho ), đồng thời giả sử ở trường hợp cơ sở , ta có . Khai triển ra ta được.

.

Trường hợp 1: Nếu với , ta có

Như vậy,  tổng trên bằng tổng dãy cấp số nhân (hệ số lũy tiến bằng ) có số hạng lớn nhất là . Như vậy, ta có

Trường hợp 2: Nếu với , tương tự ta cũng có tổng dãy cấp số nhân với hệ số lũy tiến và số hạng lớn nhất là . Như vậy, ta có

Trường hợp 3: Nếu , các số hạng của tổng trên đều bằng nhau và bằng , vậy

Ví dụ:

1. Thuật toán nhân số nguyên -bit của Karatsuba-Ofman có độ phức tạp thuật toán theo trường hợp 1 () .
2. Nếu thì theo trường hợp 2 ().
3. Thuật toán sắp xếp trộn (Merge Sort) có độ phức tạp thuật toán theo trường hợp 3.