大O作為上界
/ big OH /
大O是一個天花板。當我們說某演算法是 O(n^2)，我們承諾的是：一旦輸入夠大，它的成本成長絕不會比某個 n^2 的常數倍更快。這就像告訴朋友「這趟最多三小時」——是對成長最壞情況的保證，而不是宣稱它總是達到那個最壞值。
形式上，若存在一個正常數 c 與一個門檻 n0，使得對所有 n >= n0 都有 f(n) <= c 乘 g(n)，則稱函數 f(n) 為 O(g(n))。c 與 n0 這兩個數稱為見證常數：c 吸收常數倍率，n0 則說「我只對夠大的輸入保證這件事」。例如 3n^2 + 5n + 2 是 O(n^2)：取 c = 10、n0 = 1，確實對所有 n >= 1 都有 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2 = 10n^2，因為 n >= 1 時 n 與 1 各自都不超過 n^2。注意我們把較小的項都換成 n^2，好讓不等式容易成立——這是典型的證明技巧。
一個關鍵的誠實之處：大O是上界，所以它可能很鬆。每個是 O(n) 的函數也都是 O(n^2)，甚至是 O(2^n)，就像「最多三小時」嚴格說也是「最多一週」。所以光說 O(n^2) 並不表示成本真的像 n^2 那樣成長——只表示它成長不會更快。要把成長精確釘死，你需要大Theta。人們常把「O」隨口當作「恰好等於」，但嚴格而言它只把成長從上方封頂。
宣稱：7n + 100 是 O(n)。證明：取 c = 8、n0 = 100。對所有 n >= 100 都有 100 <= n，故 7n + 100 <= 7n + n = 8n = c 乘 n。見證常數（c = 8, n0 = 100）證實了這個界；在 n = 100 之前不等式可能不成立，這無妨，因為大O只在意大的 n。
一個大O證明，就是給出能讓不等式從某點起永遠成立的見證常數 c 與 n0。
O(g) 表示「成長不快於 g」，可能是一個鬆的天花板：一個 O(n) 的演算法（如實地說）也是 O(n^2)。只有大Theta才宣稱確切的成長率。