大Omega作為下界
/ big oh-MAY-guh /
大Omega是與大O天花板相對的地板。當我們說某成本是 Omega(n log n)，我們承諾的是：對大的輸入，它至少是某個 n log n 的常數倍——不可能比這更好。它是「至少要一小時」對應於「最多三小時」的那一半。
形式上，若存在正常數 c 與門檻 n0，使得對所有 n >= n0 都有 f(n) >= c 乘 g(n)，則稱 f(n) 為 Omega(g(n))。與大O是同樣兩個見證常數，只是不等式方向相反。例如 n^2 - 3n 是 Omega(n^2)：取 c = 1/2、n0 = 6，對所有 n >= 6 都有 3n <= (1/2)n^2（因為 n >= 6 表示 n/2 >= 3），故 n^2 - 3n >= n^2 - (1/2)n^2 = (1/2)n^2 = c 乘 n^2。我們把被減去的項從上方界住，留下乾淨的 n^2 的一個分數倍。
大Omega是描述下界的自然語言，既用於某個演算法（「光這個迴圈就已做了 Omega(n) 的工作，所以整體不可能是次線性」），也用於某個問題（「任何以比較為基礎的排序至少需要 Omega(n log n) 次比較，所以在比較模型內沒有巧計能勝過它」）。要注意範圍：問題下界說的是每個演算法都至少得付這麼多；某演算法自己的 Omega 界只描述那一個演算法。說 f 是 Omega(g)，恰好等同於說 g 是 O(f)。
宣稱：任何要印出一個 n 乘 n 表格全部 n^2 個格子的演算法都是 Omega(n^2)，因為每個格子至少要一個輸出步，而格子共有 n^2 個。無論它多巧妙，都無法低於 n^2 步——光印出答案就要花這麼多。
輸出大小論證是最簡單的下界：你至少得把答案產生出來。
對「問題」的下界（每個演算法都必須付出）比對某個特定演算法的下界強得多、也難證得多。別把兩者混為一談。