WHY BIG-O AND LITTLE-O IN ALGORITHM COMPLEXITY: A PEDAGOGICAL REMARK

In the comparative analysis of dierent algorithm, O- and o-notions are fre-quently used. While their use is productive, most textbooks do not provide a convincing student-oriented explanation of why these particular notations are useful in algorithm analysis. In this note, we provide such an explanation. 1. Formulation of the Problem O is ubiquitous in algorithm analysis. In algorithm analysis, to gauge the speed of an algorithm, usually, O-estimates are used: e.g., the algorithm requires time O(n), or O(n2), etc.; see, e.g., [1]. Often, o-estimates are also used. Need for O and o is not clearly explained. In many textbooks, the need to consider O- and o- estimates is not clearly explained. What we do in this paper. The main objective of this short paper is to ll this gap by providing the students with a simple and hopefully convincing explanation of why O and o estimates are natural. 2. Analysis of the Problem and the Explanation of O What we really want. What we want is to estimate how fast the algorithm is, i.e., how much time T (x) it takes on dierent inputs x. Worst-case and average computation time. In some situations, e.g., in auto-matic control, we need to make decisions in real time, i.e., within a certain period of time. For example, if a automatic car sees a suddenly appearing obstacle, it needs to compute the needed change in trajectory so as to have time to avoid the collision. In general, the computation time T (x) is dierent for dierent inputs x, so we want to be sure that for all these inputs, this computation time does not exceed a given threshold. In other words, we need to make sure that the worst-case time max x T (x) does not exceed this threshold. Of course, the computation time depends on the size of the input: e.g., to answer a query, we sometimes need to look at all the records in the corresponding database. Copyrigh