小o符號
/ little OH /
小o是放開煞車的大O：它說的不只是一個函數被另一個界住，而是相對於另一個最終可忽略。大O的 O(g) 允許 f 與 g 成長一樣快（在常數倍內），但 o(g) 堅持 f 成長嚴格較慢，使得比值 f/g 趨近於零。把 f(n) = o(g(n)) 想成「隨著 n 變大，f 變成 g 的一個逐漸消失的分數」。
形式上，若對「每一個」正常數 c 都存在一個（取決於 c 的）門檻 n0，使得對所有 n >= n0 都有 f(n) < c 乘 g(n)，則稱 f(n) 為 o(g(n))。與大O的關鍵差異在於量詞：大O只需要「一個」能成立的 c；小o則要求對每個 c 都成立，無論它多麼小。當極限存在時，最乾淨的判準是：f(n) 是 o(g(n)) 恰好等於 f(n)/g(n) 在 n 趨於無窮時的極限為 0。例如 n 是 o(n^2)，因為 n/n^2 = 1/n 趨於 0；而 log n 是 o(n)，因為 (log n)/n 趨於 0。
每當我們想說「這一項在漸進上被壓制、可以忽略」時，小o就會出現——它正是「低階項」的形式意義。把成本寫成 n^2 + o(n^2)，意思是「n^2 加上一些相對於 n^2 變得可忽略的東西」。注意它與大O的不對稱：n 是 O(n)，但 n 不是 o(n)，因為 n/n = 1 不趨於 0。小o是嚴格更強、嚴格小於的宣稱。
100n 是 n^2 的小o嗎？算比值 100n / n^2 = 100/n，當 n 變大時趨於 0。是的，100n = o(n^2)——巨大的常數 100 無關緊要，因為小o容許任何常數仍能取勝。但 100n 不是 o(n)：比值 100n/n = 100 固定在 100，永遠到不了 0。
小o是「比值極限等於零」的判準；面對成長更快的 g，常數救不了你。
o(g) 嚴格強於 O(g)：f = o(g) 蘊含 f = O(g)，反之不然。其定義的量詞是「對每個 c」，而非「存在某個 c」。