寫出遞迴式 T(n)
你已經會數一個迴圈的代價了。可一個呼叫*自身*的函數，代價又是多少？你沒法只盯著它看，因為它的工作量取決於同一個問題的更小副本的工作量。訣竅是給這個代價起個名字——叫它 T(n)，即求解規模為 n 的問題所需的時間——然後寫一個等式來說：「規模 n 的時間，等於更小那些部分的時間，加上我拆分與合併它們所做的一切。」這個引用自身的等式，就是[[recurrence-relation|遞迴關係（遞迴式）]]。
一旦看出規律，把程式碼讀成遞迴式就是機械活了。每出現一次遞迴呼叫，就加一個 T(更小的規模)。然後為該次呼叫中的非遞迴工作單獨加一項——也就是遞迴之前或之後發生的迴圈、比較與合併。最後寫一個基準情形（base case）：函數停止遞迴時的規模，它只花常數時間，T(1) = O(1)。下面是[[merge-sort|合併排序]]，逐行讀成它的遞迴式。
void mergeSort(vector<int>& a, int lo, int hi) {
if (hi - lo <= 1) return; // base case: T(1) = O(1)
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // one call on n/2 -> T(n/2)
mergeSort(a, mid, hi); // one call on n/2 -> T(n/2)
merge(a, lo, mid, hi); // scan and merge -> O(n)
}
// Reading the lines: T(n) = 2*T(n/2) + O(n), T(1) = O(1)用展開法求解
在動用定理之前，用老實的辦法解一個遞迴式很有幫助：展開（unrolling）。你把遞迴式一層層代入自身，直到看出規律，再把各層的工作量加起來。取最簡單的遞迴代價：T(n) = T(n/2) + O(1)——對一半做一次呼叫，加上常數工作。這正是[[binary-search|二分搜尋]]：丟掉一半，做一次比較。
T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
...
= T(n/2^k) + k // after k steps
Stop when n/2^k = 1 => 2^k = n => k = log2(n)
So T(n) = T(1) + log2(n) = O(log n).同一幅圖也能解釋合併排序，只是帳算法變了。畫出遞迴樹（recursion tree）：樹根是規模為 n 的問題，它的兩個孩子是 n/2，孩子的孩子是 n/4，依此類推。這棵樹深 log n 層——但在*每一*層上，跨越所有節點的合併加起來都是 O(n)。於是你有 log n 層，每層花 O(n)，總和就是它們的乘積：O(n log n)。
level 0: [ n ] work this level: n
level 1: [n/2] [n/2] work this level: n/2 + n/2 = n
level 2: [n/4][n/4][n/4][n/4] work this level: 4*(n/4) = n
... ... ... ... ... ...
level log n: [1][1][1] ... [1] work this level: n*(1) = n
----------------------------------------------------
log n levels x n per level = O(n log n)把主定理當作食譜
展開法管用，但很繁瑣。[[master-theorem|主定理]]是針對一種特定形式的[[divide-and-conquer|分治]]遞迴式的捷徑：T(n) = a·T(n/b) + f(n)，其中你做 a 次遞迴呼叫，每次面對一個小 b 倍的問題，並在遞迴之外花 f(n) 做拆分與合併的工作。對合併排序，a = 2、b = 2、f(n) = n。該定理把遞迴本身的增長（由 n 的「以 b 為底 a 的對數」次冪刻畫）與 f(n) 的增長相比較，挑出勝者。
Master Theorem (for T(n) = a*T(n/b) + f(n), a >= 1, b > 1)
Let c = log_b(a). Compare f(n) against n^c:
Case 1 f(n) grows slower than n^c -> T(n) = O(n^c)
(the leaves dominate)
Case 2 f(n) grows like n^c -> T(n) = O(n^c * log n)
(every level costs about the same)
Case 3 f(n) grows faster than n^c -> T(n) = O(f(n))
(the root's own work dominates)- 合併排序：T(n) = 2·T(n/2) + n。此處 a = 2、b = 2，故 c = log_2(2) = 1，n^c = n。額外工作 f(n) = n 與 n^c = n 同階——打平。這是情形 2，得 T(n) = O(n^1 · log n) = O(n log n)。與遞迴樹完全吻合。
- 二分搜尋：T(n) = 1·T(n/2) + O(1)。此處 a = 1、b = 2，故 c = log_2(1) = 0，n^c = n^0 = 1。額外工作 f(n) = O(1) 與 n^c = 1 同階——又是打平。仍是情形 2，得 T(n) = O(1 · log n) = O(log n)。和展開法給出的答案一致。
- 嚐一口情形 1：T(n) = 8·T(n/2) + n。此時 c = log_2(8) = 3，故 n^c = n^3，遠快於 f(n) = n。葉子主導：T(n) = O(n^3)。是遞迴的分支數、而非每次呼叫的工作量，決定了代價。