Michael Data

The [http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm) competetive ratio] of an online algorithm is the ratio of the algorithm's performance to the optimal offline algorithm for worst-case and best-case input.