An analysis in which the performance of an on-line algorithm is compared to the best that could have been achieved if all the inputs had been known in advance.