Algorithms in a Nutshell

One Final Point

We have simplified the presentation of the "Big O" notation in this book. For example, when discussing the behavior of the ADDITION algorithm that is linear with respect to its input size n, we argued that there exists some constant c>0 such that t(n)≤c×n for all n>n₀; recall that t(n) represents the actual running time of ADDITION. By this reasoning, we claim the performance of ADDITION is O(n). The careful reader will note that we could just as easily have used a function f(n)=c*2ⁿ that grows more rapidly than c*n. Indeed, although it is technically accurate to claim that ADDITION is O(2ⁿ), such a statement provides very little information (it would be like saying that you need no more than one week to perform a five-minute task). To explain why, consider the notation Ω(g(n)), which declares that g(n)≤t(n) is a lower bound for the actual running time. One can often compute both the upper (O) and lower (Ω) bound for the execution time of an algorithm, in which case the appropriate notation to use is Θ(f(n)), which asserts that f(n) is asymptotically both an upper bound (as is the case for O(f(n)) and a lower bound for t(n).

We chose the more informal (and widely accepted use) of O(f(n)) to simplify the presentations and analyses. We ensure that when discussing algorithmic behavior, there is no better f'(n) that can be used to classify the algorithms we have identified as O(f(n)).