最壞情況分析（worst-case analysis）
想像在規劃通勤要花多久。你可以報一個道路淨空的完美日子（最佳情況）、一個普通日子（平均情況），或是塞車加道路施工的最糟日子（最壞情況）。必須保證準時的工程師在乎的是最後那個，因為只在幸運日子才成立的承諾根本不算承諾。最壞情況分析對演算法施以同樣的謹慎：在所有大小為 n 的輸入之中，量出該演算法可能花的最大步數。
形式上，最壞情況時間 T(n) 是：取遍每個大小為 n 的輸入，機器在那個輸入上所做步數的最大值。我們先對固定大小的輸入取最壞，再觀察那個最壞值如何隨 n 成長。這給了我們一個保證——一個任何該大小的輸入都不會超過的上界——這正是我們宣告某問題屬於 P 時所要的東西。這也是為什麼你看到的執行時間（例如好的排序為 O(n log n)）若未特別聲明，都是最壞情況的界。
最壞情況之所以是複雜度理論的預設，是因為它穩健且可證明，但要誠實面對它的盲點：最壞情況可能很罕見。一個著名例子是線性規劃的單純形法，它在最壞情況下是指數級的，但在實務出現的輸入上卻快如閃電；快速排序在最壞情況下是 O(n^2)，平均卻是 O(n log n)。所以最壞情況分析可能過度悲觀。這正是複雜度理論也研究平均情況、以及（之後的）隨機化與參數化分析的原因，但最壞情況仍是定義 P 這類經典類別的保守基準線。
在 n 個項目的清單裡線性搜尋某值：最佳情況它是第一個項目（1 步）；平均情況約 n/2 步；最壞情況它不存在或在最後，要花掉全部 n 步。我們回報 O(n)，也就是最壞情況，因為那是無論來的是哪個輸入都成立的保證。
同一演算法的最佳、平均與最壞情況；複雜度理論以最壞情況作為保證的預設。
最壞情況是一種保證，但它可能過度悲觀：一個最壞情況時間很差的演算法（如單純形法或快速排序）在實際出現的輸入上仍可能表現極佳。