遞迴式的基底情況（base case of a recurrence）
像 T(n) = 2 T(n/2) + n 這樣的遞迴式，告訴你如何從較小的值得到 T(n)——但它自己永遠不會見底。你需要一個起點：對最小輸入成本的陳述，遞迴在那裡停下，直接做固定量的工作。那個起點就是基底情況。
具體而言，基底情況形如 T(1) = Theta(1)（或對 n <= 某個小常數時 T(n) = Theta(1)）。它說：當問題夠小，就直接用常數時間解，而不再遞迴。這裡發生了兩件事。第一，它讓遞迴式有良好定義——沒有它，展開 T(n/2)、T(n/4)…… 會永無止境地下降。第二，它在代入法中為歸納奠基：你明確地對基底情況證明界成立，再由歸納步驟把它提升到所有 n。在遞迴樹裡，基底情況恰好就是葉子，而葉子的數量正是給出 n^(log_b a) 的東西。
以下是誠實又令人安心的部分：對「漸進」分析而言，基底的確切值幾乎從不重要。無論 T(1) = 1 還是 T(1) = 1000，Theta 界都一樣，因為常數的基底只會把答案平移一個常數因子。這就是教科書放心地假設 T(1) = Theta(1)、甚至對所有小 n 都假設 T(n) = Theta(1)，然後繼續往下走的原因。但基底情況「並非可有可無」：沒有基底的遞迴式什麼都沒描述，而在代入法中，未檢查的基底情況是真正的漏洞——你確實必須確認猜出的界在最底層成立，並選好常數使它成立，歸納才有效。
對 T(n) = 2 T(n/2) + n 且 T(1) = 1：遞迴在規模 1 停下，那裡有 n 個葉子、各花費 1（合計 n），加上 log n 層、每層花費 n，得 Theta(n log n)。把 T(1) 改成 5 對漸進結果毫無影響——它只是把葉子總量乘以 5。
基底情況為遞迴奠基（即葉子）；它確切的常數不會改變 Theta 界。
漸進上，基底常數無關緊要，但基底情況本身是必要的——既為了讓遞迴式有良好定義，也為了錨定歸納。在代入法中，忘記驗證基底情況是真正的邏輯漏洞，不是形式。