證明一個漸進界
知道定義是一回事；真正證明「f(n) 是 O(g(n))」則是一項有套路的技能。好消息是，幾乎每個常規的界都遵循同樣那幾個步驟，看過幾次就會變成機械動作。目標是產生上一條提到的見證者 c 與 n0。
上界的標準套路：(1) 把 f(n) 展開成各項之和。(2) 對每一項，找一個 g(n) 的常數倍，在 n 夠大時不小於它——通常是把較小的 n 的次方換成 g(n)，利用「n >= 1 時，若 a <= b 則 n^a <= n^b」。(3) 把這些常數加起來得到單一的 c。(4) 記下你所需的最大門檻作為 n0。舉個做過的例子，證明 4n^2 + 2n + 7 是 O(n^2)：對 n >= 1，2n <= 2n^2 且 7 <= 7n^2，故 4n^2 + 2n + 7 <= 4n^2 + 2n^2 + 7n^2 = 13n^2。完成，c = 13、n0 = 1。下界則反過來捨去或低估項：4n^2 + 2n + 7 >= 4n^2，得 Omega(n^2)。兩個方向合起來給出 Theta(n^2)。
值得背下來的常用動作：有限多項之和是其最大項的大O；一個常數乘上函數不改變其階；而以極限為基礎的證明則計算 f(n)/g(n)，看它是否趨於常數（Theta）、零（o）或無窮（omega）。一個誠實的陷阱：你必須讓 c 與 n0 固定且不依賴於 n——一個偷偷讓 c 隨 n 成長的「證明」什麼也沒證，因為那樣它根本就不是一個常數倍率。
證明 n^3 + 100n^2 是 O(n^3) 但「不是」O(n^2)。上界：對 n >= 1，100n^2 <= 100n^3，故 n^3 + 100n^2 <= 101n^3，得 O(n^3)，c = 101、n0 = 1。不是 O(n^2)：若 n^3 + 100n^2 <= c n^2 對所有大 n 成立，兩邊除以 n^2 得 n + 100 <= c，對固定的 c 在 n 成長時不可能。故不存在見證者。
要推翻一個大O界，證明所需的 c 必須隨 n 成長。
c 與 n0 必須是一次選定的常數，而非依賴 n 的量。一個需要 c 隨 n 成長的界，不是有效的大O證明。