代入法（substitution method）
有時確認執行時間最乾淨的辦法就是最直接的辦法：先猜出答案，再證明你的猜測正確。這感覺像作弊——你先把結論寫下來——但誠實之處正在證明：猜錯了，就單純證不出來。
代入法有兩步。第一，猜一個封閉形式的界，例如 T(n) = O(n log n)。第二，把這個猜測代入遞迴式，用數學歸納法證明：假設對所有比 n 小的規模此界成立（歸納假設），代入後證明它對 n 也成立。具體而言，要證明 T(n) = 2 T(n/2) + n 是 O(n log n)，猜 T(n) <= c n log n。假設 T(n/2) <= c (n/2) log(n/2)。則 T(n) <= 2 c (n/2) log(n/2) + n = c n (log n - 1) + n = c n log n - c n + n，只要 c >= 1，這就 <= c n log n。歸納成立，故界成立。
兩個實務要點讓它保持誠實。你必須選好常數 c（以及基底情況的範圍），使不等式對「某門檻以上的所有 n」都封閉，而不是只對某個方便的數值成立。另外，此法只能驗證你已經懷疑的界——它不會替你發現答案；要發現答案得先畫遞迴樹。一個著名陷阱是：必須減去一個低階項，代數才封得起來：要證 T(n) = 2 T(n/2) + 1 是 O(n)，猜 T(n) <= c n 會失敗，但較強的猜測 T(n) <= c n - d 卻成功——強化歸納假設往往就是解法。
證明 T(n) = T(n-1) + n 是 O(n^2)。猜 T(n) <= c n^2。則 T(n) <= c (n-1)^2 + n = c n^2 - 2 c n + c + n = c n^2 - (2c - 1) n + c，只要 c >= 1 且 n >= 1，這就 <= c n^2。歸納假設得以維持，所以 T(n) = O(n^2)。
把猜測代入，推動代數，直到右邊重新出現同一個界。
草率使用會藏住致命錯誤：你必須在兩邊得到「相同的常數 c」，而不是最後寫個 O(...) 就算。寫成「T(n) <= 2 c (n/2) + n = c n + n = O(n)」是錯的——多出來的 +n 表示 c 這個界並沒有封起來；你只證明了單步的 O(n)，沒有完成歸納。