In computer science (or, more properly, complexity theory), we are often interested to know how a certain capability affects the complexity of a given problem. A random algorithm is obviously at least as good as a deterministic one (since it can simply avoid making any random choices); but can a nonrandom algorithm be "almost as good"? An online algorithm can never do better than the optimal offline algorithm, but how much worse does it have to be?
Competitive analysis is a way of measuring this. It provides an important handle on appreciating the inherent usefulness of certain computational capabilities (or the inherent problems in certain settings...). An algorithm A (to solve some problem P) is said to be c-competitive (with respect to an "easier" problem P', which may at least be solved by a trivial reduction of any solution to P), if for any input I, the complexity (or cost, or gain) is at most c times worse than the complexity achieved by O, an optimal algorithm to solve P', given the same input I. (The measure of complexity is identical in P and P', of course.)
Random algorithms are a simple example: a nonrandom algorithm is 3-competitive if it is never more than 3 times as bad as the optimal random algorithm. Online algorithms make things a little harder: in P, the algorithm is required to return output (several times), given some prefix of the input stream; in P', the algorithm is given the "entire input", or rather (since the stream may be infinite), it may "guess" anything it requires about the input. More formally, the optimal offline algorithm is considered to be one that, for every possible input, minimises the possible complexity (maximises the gain).
Usually, working in some field (e.g. online algorithms, mentioned above), you have some standard "reference situation" (in this case, the optimal offline algorithm), which clearly defines a P' for every P. Here are some typical results you might aim for, in increasing order of usefulness:
- Sometimes the optimal algorithm to solve P' is obvious. If not, find it (and prove optimality). Failing that, find bounds on optimal complexity
- Find a c-competitive algorithm to solve P. Try for minimal c. If c depends on various parameters of P, there may be various meanings for "minimal c". As usual in complexity theory, you might end up with only asymptotic or big-oh notation bounds.
- Prove c is optimal, or at least bound the optimal c, and approach the bound as best you can. Alternatively, prove there can be no c-competitive algorithm at all! (Yes, it happens.)
See online algorithm for an important use of this, and Ski Rental Problem for a very simple actual case.