見證常數 c 與 n0

每個大O、大Omega或大Theta的宣稱，在記號之下，都是這種形式的承諾：「從某點之後，一個函數維持在另一個函數的常數倍之內」。讓這個承諾具體化的兩個數，就是見證常數：c，那個常數倍；以及 n0，界開始成立的那一點。證明一個漸進宣稱，字面上就是把這兩個見證者拿出來。

把它們想成對兩個問題的回答。常數 c 回答「在幾倍之內？」——它吸收例如 3n 與 n 的差別，讓你不必追蹤確切係數。門檻 n0 回答「從多大的規模開始？」——它讓你忽略小 n 時的雜亂行為，那裡低階項可能主導。對大O，你需要單一一對 (c, n0)，使對所有 n >= n0 都有 f(n) <= c 乘 g(n)。關鍵是，你不需要最小可能的 c 或 n0；任何能成立的一對都能證明這個界。若 c = 5、n0 = 1 可行，那 c = 1000、n0 = 1 也可行——對 c 大方一點往往讓代數變得輕而易舉。

這就是為什麼漸進證明像一個小遊戲：改寫 f(n)，對夠大的 n 把每一項界成 g(n) 的某個倍數，把這些倍數加起來得到 c，並記下你的界開始生效的那個 n 作為 n0。見證者並不唯一，你可以挑方便的。同樣的套路適用於 Omega（改成 >=）與 Theta（兩個常數 c1 與 c2，兩邊各一）。