Mancando alcuni dati di ingresso, il costo della strategia offerta da un'algoritmo online sarà superiore rispetto a quello che un algoritmo offline può offrire. Lo studio dell'efficienza di questo tipo di algoritmiL'analisi ècompetitiva limitatopermette daldi fattovalutare cheun parametro detto α-competitività (o c-competitività) di un algoritmo online. Dato un algoritmo online A, inil generecui costo è C<sub>A</sub> ed un algoritmo offline ottimo OPT il cui costo è C<sub>OPT</sub>, nonl'algoritmo siA conosceè laα-competitivo [[variabilese casuale|distribuzioneper diogni probabilità]]possibile deisequenza possibilidi input cheσ si possonoha: avere.
Per lo studio di questo tipo di algoritmi si utilizza quindi una tecnica detta ''analisi competitiva''<ref>D. Sleator e R. E. Tarjan. ''Amortized efficiency of list update and paging rules'', ''Communications of the ACM'', 1985, 28, 202-208.</ref>, che consiste nel rapportare il costo dell'algoritmo online al costo dell'algoritmo offline ottimo che risolve il medesimo problema conoscendo tutti gli input sin dall'inizio.
L'analisi competitiva permette di valutare un parametro detto α-competitività (o c-competitività) di un algoritmo online. Dato un algoritmo online A, il cui costo è C<sub>A</sub> ed un algoritmo offline ottimo OPT il cui costo è C<sub>OPT</sub>, l'algoritmo A è α-competitivo se per ogni possibile sequenza di input σ si ha:
