遞迴樹法（recursion-tree method）

如果你在紙上追蹤一個遞迴演算法，這些呼叫會自然地展開成一棵樹：原問題在樹根，它的子問題是子節點，子問題的子問題是孫節點，一路往下直到葉子上的基底情況。遞迴樹法就是把這棵樹畫出來，在每個節點標上它「在本地」所做的工作，然後全部加起來。

以 T(n) = 2 T(n/2) + n 為例，步驟如下。在樹根寫上 n：那是最上層的合併成本。樹根有兩個子節點，各是規模 n/2 的問題，各自在本地花費 n/2，所以下一層的總和是 2 * (n/2) = n。每個子節點又各分成兩個規模 n/4、花費 n/4 的問題，所以這一層的總和又是 4 * (n/4) = n。每一層的總和都是 n。這棵樹有 1 + log2(n) 層（把 n 一路減半到 1），所以總計約為 n * (1 + log2 n) = Theta(n log n)。訣竅是找出「每層的總和」與「層數」，再相乘（當每層總和不是常數時，則把一個級數加起來）。

遞迴樹是形成猜測最好用的工具，尤其當每層的工作量會變化時。若每層總和呈幾何級數成長（越靠近葉子越大），則葉子主導，總量為 Theta(葉子數)；若往葉子方向呈幾何級數縮小，則樹根主導，總量為 Theta(f(n))；若維持持平，你就得到一個對數因子。它誠實的侷限是：手畫的樹是一種啟發式。取整與不均的切割使它只是近似，所以要得到嚴謹結果，得用代入法確認猜出的界，或直接引用主定理。