The normal methods of analysis of online algorithms usually employ the techniques of average-case analysis, making assumptions about the distribution of the inputs. In competitive analysis, we compare the performance of the online algorithm to that of an optimal offline algorithm, which would have full knowledge of future inputs. Consequently, competitive analysis is much like worst-case analysis.

This book presents a detailed introduction to the methods of competitive analysis. It contains numerous examples, such as list accessing, network routing, k-server systems, load balancing, search, decision theory, and game-theoretic applications. This well-written book will be of interest to students and researchers in algorithms and operations research.