主定理情況二（master-theorem case 2）
有些分治演算法感覺完美平衡：遞迴樹的每一層所做的總工作量都差不多。合併排序是經典例子——在頂層切割再合併花費 Theta(n)，而每一層深度的合併加起來也都是 Theta(n)。情況二正是這種平衡情形，也是那個著名的額外 log n 因子的來源。
情況二適用於 f(n) = Theta(n^(log_b a))——合併成本恰好與臨界項相符。此時 T(n) = Theta(n^(log_b a) log n)。為什麼有 log？透過樹來看：每一層的總和都是 Theta(n^(log_b a))（往下走時每層工作既不增也不減），而層數有 Theta(log n) 層，因為規模每步縮小 b 倍直到抵達基底情況。把每層工作乘上層數，就得到 n^(log_b a) log n。以合併排序為例，log_2 2 = 1，f(n) = n = Theta(n^1)，所以 T(n) = Theta(n log n)。
只要每層工作持平，就會出現這個情況，這也解釋了為什麼 O(n log n) 對優良的分治排序與類似演算法如此常見。情況二有一個更廣義的版本，允許 f(n) = Theta(n^(log_b a) log^k n)（k >= 0），得到 T(n) = Theta(n^(log_b a) log^(k+1) n)——每多一個既有的 log，最後那個 log 的次方就加一。誠實的告誡：f(n) 必須與 n^(log_b a) 相符到一個常數（或這種 log 次方）；若兩者差一個真正的 n 次方，你就在情況一或情況三，而不在此。
T(n) = 2 T(n/2) + Theta(n)：log_2 2 = 1 且 f(n) = Theta(n) = Theta(n^1)，完全相符，故情況二給出 T(n) = Theta(n log n)——這正是合併排序，以及隨機快速排序平均情況的分割遞迴式。
當 f(n) 等於 n^(log_b a) 時，每層成本相同，而 log n 層帶來一個額外的 log 因子。
答案裡的 log n 不是來自 f(n)——它是樹的「層數」。常見的混淆是以為這個 log 來自合併步驟；其實它來自「n 能被對折幾次」。