為什麼使用漸進分析
想像兩位廚師比賽切菜，一位的刀稍快、一位稍慢。要切三根紅蘿蔔時，刀快不快幾乎沒差；但若要切一萬根，決定勝負的是切法本身，而不是那把刀。漸進分析就是對演算法問同樣的問題：不是某台機器、某筆輸入跑得多快，而是當輸入越來越大時，執行時間如何成長。
做法是把成本表示成輸入規模 n 的函數，然後只保留在 n 很大時主導這個函數的部分。我們刻意丟掉兩類細節。第一是常數倍率：若一種方法做 5n 步、另一種做 100n 步，兩者都是線性成長，我們都稱為「n 階」，因為硬體速度、語言與編譯器本來就會吸收常數倍率。第二是低階項：成本 n^2 + 3n + 7 在 n 很大時由 n^2 主導，因為 n = 1000 時 n^2 項是一百萬，而 3n + 7 不過三千出頭。所以我們回報 n^2，其餘捨去。剩下的就是成長的形狀。
這之所以重要，是因為它給出一個能跨越機器、語言或輸入而不變的預測。成長像 n^2 的演算法，最終一定會輸給成長像 n log n 的，無論在誰的筆電上跑，因為兩者的差距會隨 n 無上限地拉開。誠實的提醒是：漸進描述的是成長趨勢，不是每個規模下的判決；在 n 很小時，被丟掉的常數與低階項可能完全顛覆排名，這正是我們說「最終」的原因。
方法 A 做 100n 個基本步；方法 B 做 n^2 個。當 n = 10，A 做 1000 步、B 只做 100，B 勝。當 n = 100 兩者打平於 10000。當 n = 1000，A 做 100000、B 做 1000000，A 以 10 倍勝出；當 n = 1,000,000 時 A 勝出一萬倍。n = 100 的交叉點正是被丟掉的常數不再重要之處。
常數決定小 n 的比賽，成長率決定大 n 的比賽。
漸進分析預測成本如何隨規模成長，而非在你實際輸入上哪個演算法最快；在 n 很小時，漸進較「差」的方法反而可能是實務上的贏家。