主方法求解遞歸式

遞歸式描述一種演算法運行時間：

它將規模為的問題分解為個子問題，每個子問題的規模為，其中和都為正常數。個子問題遞歸的求解，每個花費時間為。函數包含了問題分解和子問題解合併的代價。

主定理

令和是常數，是一個函數，是定義在非負整數上的遞歸式：

有如下漸近界：

1. 若對某個常數有，則。
2. 若，則。
3. 若對某個常數有，且對某個常數和所有足夠大的有，則。

對於三種情況中的每一種，我們將函數和函數進行比較，較大者決定了遞歸式的解。若函數 更大，如情況1，若函數更大，如情況3，若二者相當，如情況2。

情況3比較棘手，所以祈求碰到的問題小一點。