worst-case analysis

Imagine planning how long a commute might take. You could quote the time on a perfect day with empty roads (best case), or a typical day (average case), or the worst rush-hour-plus-roadworks day (worst case). Engineers who must guarantee a deadline care about the last one, because a promise that holds only on lucky days is no promise at all. Worst-case analysis applies the same caution to algorithms: among all inputs of size n, it measures the largest number of steps the algorithm could possibly take.

Formally, the worst-case time T(n) is the maximum, over every input of size n, of the number of steps the machine makes on that input. We take the worst over inputs of a fixed size, then watch how that worst grows as n grows. This gives a guarantee, an upper bound that no input of that size can exceed, which is exactly what we want when we declare a problem to be in P. It is also why the running times you see, like O(n log n) for a good sort, are worst-case bounds unless explicitly stated otherwise.

Worst-case is the default in complexity theory because it is robust and provable, but be honest about its blind spot: the worst case may be rare. A famous example is the simplex method for linear programming, which is exponential in the worst case yet blazingly fast on the inputs that arise in practice; quicksort is O(n^2) in the worst case but O(n log n) on average. So worst-case analysis can be pessimistic. That is why complexity theory also studies average-case and (later) randomized and parameterized analyses, but worst-case remains the conservative baseline that defines the classic classes like P.