Competitive analysis is a method invented for analyzing
online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal
offline algorithm that can view the sequence of requests in advance. An algorithm is
competitive if its
competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional
worst-case analysis, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm.