主定理（master theorem）
每次都用手解分治遞迴式很煩，而且同樣三種模式一再出現。主定理是一張查詢表，只要你的遞迴式恰好是 T(n) = a T(n/b) + f(n) 這個形狀，就能直接把它變成答案。它是演算法分析中最常被使用的捷徑。
它的運作方式是比較兩個量。遞迴部分想把工作量推升到 n^(log_b a)（即所有工作都落在葉子上時的成本，其中 log_b a 是臨界指數）。合併部分每層貢獻 f(n)。定理把 f(n) 拿來和 n^(log_b a) 比較：情況一——f(n) 在多項式意義上較小，於是葉子主導，T(n) = Theta(n^(log_b a))。情況二——兩者一樣大（f(n) = Theta(n^(log_b a))），每層成本大致相同，出現一個對數因子，得 T(n) = Theta(n^(log_b a) log n)。情況三——f(n) 在多項式意義上較大且滿足正則條件，於是樹根主導，T(n) = Theta(f(n))。以 T(n) = 2 T(n/2) + n 為例：log_2 2 = 1，n^1 = n 等於 f(n) = n，故情況二給出 Theta(n log n)。
謹慎使用幾乎像魔法，但要誠實面對它的侷限。它只適用於等分形式 a T(n/b) + f(n)；不均切割需要阿克拉-巴齊方法。它要求 a >= 1 且 b > 1，而 f(n) 必須相當規矩。關鍵在於存在「縫隙」：在情況一與情況二之間、以及情況二與情況三之間，這個比較必須差一個多項式因子（差一個 n^epsilon，某個 epsilon > 0），所以像 T(n) = 2 T(n/2) + n / log n 這種遞迴式落在縫隙裡，基本主定理對它什麼都沒說——你得用遞迴樹法或它的擴充版本。
二分搜尋：T(n) = T(n/2) + Theta(1)。此處 a = 1、b = 2、log_2 1 = 0、n^0 = 1，且 f(n) = Theta(1) = Theta(n^0)，故適用情況二，T(n) = Theta(n^0 log n) = Theta(log n)。合併排序同樣落在情況二；史特拉森（a=7, b=2）落在情況一，得 Theta(n^(log_2 7)) ≈ Theta(n^2.81)。
算出 log_b a，把 n^(log_b a) 與 f(n) 相比，再讀出對應的情況。
主定理並不涵蓋所有遞迴式。各情況的比較需要一個多項式差距，所以像 f(n) = n log n（當 n^(log_b a) = n 時）這類函數落在情況之間，基本主定理保持沉默——別硬把三種情況之一套到它們身上。