CS 860 | SCS

Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved algorithm can be obtained by considering a finer partition of the input space. For instance, the best algorithm to compute the convex hull of n points in the plane has worse case complexity O(n log n), but a better algorithm is known with complexity O(n log h), where h is the number of vertices on the convex hull. Since h is never greater than n the latter algorithm is never worse and often better than one which only optimizes for the worst case.