寫出執行時間的遞迴關係式（running-time recurrence）

想像你請朋友幫忙數一排很長的隊伍裡有多少人。與其自己一個一個數，你把隊伍從中間切成兩半，各交給一位幫手，等他們各自回報數字，再把兩個數字加起來，外加你自己切隊伍花的一點功夫。要知道這整件事花多少時間，你就用「較小工作的花費」來描述「整個工作的花費」。這種自我參照的描述，就是遞迴關係式。

具體來說，執行時間的遞迴關係式是一條方程式，用較小規模的 T 來表示 T(n)，也就是規模為 n 的輸入所需的時間。你直接從演算法讀出它：數一數有幾個遞迴呼叫、各自的規模是多少，再加上這一層所做、與遞迴無關的工作。例如合併排序（merge sort）對半邊各做一次遞迴呼叫，再用線性時間合併，因此 T(n) = 2 T(n/2) + O(n)；二分搜尋（binary search）只對一半遞迴並多做 O(1) 的工作，所以 T(n) = T(n/2) + O(1)。務必為遞迴式配上一個基底情況（base case），例如 T(1) = O(1)，否則它在最底層什麼都沒描述。

寫出遞迴式是分析任何遞迴演算法的第一步，也是最容易出錯的一步：一旦寫對，你就能用遞迴樹、代入法或主定理（master theorem）來求解。常見錯誤包括數錯呼叫次數（卡拉楚巴乘法做三次半規模乘法，不是四次）、忘了合併的成本，或把子問題規模標錯（究竟是 n/2 還是 n-1？）。誠實的分析會謹慎處理向上、向下取整，例如 T(ceil(n/2)) 與 T(floor(n/2))，不過對漸進分析而言它們幾乎不會改變結果。