大Theta作為緊界
/ big THAY-tuh /
大Theta是當你確切知道成長率、而不只知道單邊界時所用的記號。說某成本是 Theta(n log n)，意思是它從兩個方向都像 n log n 那樣成長：對大的輸入，它被夾在 n log n 的兩個常數倍之間。若大O是天花板、大Omega是地板，那大Theta就是天花板與地板形狀相同、把函數釘在原地的情況。
形式上，若存在正常數 c1、c2 與門檻 n0，使得對所有 n >= n0 都有 c1 乘 g(n) <= f(n) <= c2 乘 g(n)，則稱 f(n) 為 Theta(g(n))。等價地（這是好用的版本），f 是 Theta(g) 恰好等於 f 同時是 O(g) 與 Omega(g)。所以要證 Theta 界，就分別證天花板與地板。對 3n^2 + 5n + 2，我們已看到它 <= 10n^2（O 那邊）；而顯然 3n^2 + 5n + 2 >= 3n^2（Omega 那邊，c1 = 3），所以它是 Theta(n^2)：取 c1 = 3、c2 = 10、n0 = 1。
Theta 是多數人隨口說「O」時其實想表達的那個精確、誠實的宣稱。「合併排序是 Theta(n log n)」告訴你執行時間真的像 n log n 那樣成長——不更快、不更慢——這比單純一個上界資訊豐富得多。當一個問題的最佳演算法與一個已證的下界相符時，兩者在某個 Theta 相遇，我們說該問題在漸進意義下「已解決」；比較式排序在 Theta(n log n) 就是經典例子。
一個雙重迴圈，外層索引 i 從 1 到 n、內層跑 i 次，共做 1 + 2 + ... + n = n(n+1)/2 步，等於 (1/2)n^2 + (1/2)n。它是 Theta(n^2)：對 n >= 1，下界為 (1/2)n^2、上界為 n^2。我們得到兩個方向都精確的成長，而不只是「最多 n^2」。
分別證 O 與 Omega；兩者相符時，你就有了 Theta。
f = Theta(g) 需要在同一成長率上「同時」有上界與下界。若真實成長更小（例如實為線性的成本），函數可以是 O(n^2) 卻不是 Theta(n^2)。