A.2 Order Analysis of FunctionsIn the analysis of algorithms, it is often cumbersome or impossible to derive exact expressions for parameters such as run time, speedup, and efficiency. In many cases, an approximation of the exact expression is adequate. The approximation may indeed be more illustrative of the behavior of the function because it focuses on the critical factors influencing the parameter. Example A.1 Distances traveled by three cars Consider three cars A, B, and C. Assume that we start monitoring the cars at time t = 0. At t = 0, car A is moving at a velocity of 1000 feet per second and maintains a constant velocity. At t = 0, car B 's velocity is 100 feet per second and it is accelerating at a rate of 20 feet per second per second. Car C starts from a standstill at t = 0 and accelerates at a rate of 25 feet per second per second. Let D_{A}(t), D_{B} (t), and D_{C} (t) represent the distances traveled in t seconds by cars A, B, and C. From elementary physics, we know that Now, we compare the cars according to the distance they travel in a given time. For t > 45 seconds, car B outperforms car A. Similarly, for t > 20 seconds, car C outperforms car B, and fort > 40 seconds, car C outperforms car A. Furthermore, D_{C} (t) < 1.25 D_{B} (t) and D_{B} (t) < D_{C} (t) for t > 20, which implies that after a certain time, the difference in the performance of cars B and C is bounded by the other scaled by a constant multiplicative factor. All these facts can be captured by the order analysis of the expressions. The Q Notation: From Example A.1, D_{C} (t) < 1.25 D_{B}(t) and D_{B}(t) < D_{C} (t) for t > 20; that is, the difference in the performance of cars B and C after t = 0 is bounded by the other scaled by a constant multiplicative factor. Such an equivalence in performance is often significant when analyzing performance. The Q notation captures the relationship between these two functions. The functions D_{C}(t) and D_{B}(t) can be expressed by using the Q notation as D_{C}(t) = Q(D_{B}(t)) and D_{B}(t) = Q(D_{C}(t)). Furthermore, both functions are equal to Q(t^{2}). Formally, the Q notation is defined as follows: given a function g(x), f(x) = Q(g(x)) if and only if for any constants c_{1}, c_{2} > 0, there exists an x_{0} 0 such that c_{1}g(x) f (x) c_{2} g(x) for all x x_{0}. The O Notation: Often, we would like to bound the growth of a particular parameter by a simpler function. From Example A.1 we have seen that for t > 45, D_{B}(t) is always greater than D_{A} (t). This relation between D_{A}(t) and D_{B}(t) is expressed using the O (bigoh) notation as D_{A}(t) = O (D_{B}(t)). Formally, the O notation is defined as follows: given a function g(x), f (x) = O (g(x)) if and only if for any constant c > 0, their exists an x_{0} 0 such that f (x) cg(x) for all x x_{0}. From this definition we deduce that D_{A}(t) = O(t^{2}) and D_{B}(t) = O(t^{2}). Furthermore, D_{A}(t) = O (t) also satisfies the conditions of the O notation. The W Notation: The O notation sets an upper bound on the rate of growth of a function. The W notation is the converse of the O notation; that is, it sets a lower bound on the rate of growth of a function. From Example A.1, D_{A}(t) < D_{C} (t) for t > 40. This relationship can be expressed using the W notation as D_{C} (t) = W(D_{A}(t)). Formally, given a function g(x), f (x) = W(g(x)) if and only if for any constant c > 0, there exists an x_{0} 0 such that f (x) cg(x) for all x x_{0}. Properties of Functions Expressed in Order NotationThe order notations for expressions have a number of properties that are useful when analyzing the performance of algorithms. Some of the important properties are as follows:
