The competitive ratio of an online algorithm measures its worst-case performance relative to an optimal algorithm
that knows the entire input in advance. For a cost-minimization problem, let 
be the cost incurred by an online algorithm on a finite input sequence 
, and let 
be the minimum cost achievable with advance knowledge
of 
.
The online algorithm is 
-competitive if
 |
where 
is a constant independent of 
, though it may depend on the initial state. The competitive
ratio is the infimum of the admissible values of 
. Strict competitiveness requires 
(Borodin and El-Yaniv 1998).
For a randomized online algorithm, the comparison uses the expected value of the cost. The resulting competitive ratio depends on the adversary model, including whether the adversary can adapt future inputs to the algorithm's random choices. Thus deterministic and randomized competitive ratios need not agree.
The deterministic k-server problem asks for an online algorithm whose competitive ratio
is 
on every metric space with at least 
points.
