Table of Contents Previous Section Next Section

A.2 Order Analysis of Functions

In 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 DA(t), DB (t), and DC (t) represent the distances traveled in t seconds by cars A, B, and C. From elementary physics, we know that

graphics/apafig01.gif


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, DC (t) < 1.25 DB (t) and DB (t) < DC (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, DC (t) < 1.25 DB(t) and DB(t) < DC (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 DC(t) and DB(t) can be expressed by using the Q notation as DC(t) = Q(DB(t)) and DB(t) = Q(DC(t)). Furthermore, both functions are equal to Q(t2).

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 c1, c2 > 0, there exists an x0 0 such that c1g(x) f (x) c2 g(x) for all x x0.

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, DB(t) is always greater than DA (t). This relation between DA(t) and DB(t) is expressed using the O (big-oh) notation as DA(t) = O (DB(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 x0 0 such that f (x) cg(x) for all x x0. From this definition we deduce that DA(t) = O(t2) and DB(t) = O(t2). Furthermore, DA(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, DA(t) < DC (t) for t > 40. This relationship can be expressed using the W notation as DC (t) = W(DA(t)).

Formally, given a function g(x), f (x) = W(g(x)) if and only if for any constant c > 0, there exists an x0 0 such that f (x) cg(x) for all x x0.

Properties of Functions Expressed in Order Notation

The 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:

  1. xa = O(xb) if and only if a b.

  2. loga (x) = Q(logb(x)) for all a and b.

  3. ax = O (bx) if and only if a b.

  4. For any constant c, c = O (1).

  5. If f = O (g) then f + g = O (g).

  6. If f = Q(g) then f + g = Q(g) = Q(f).

  7. f = O (g) if and only if g = W(f).

  8. f = Q(g) if and only if f = W(g) and f = O(g).
    Table of Contents Previous Section Next Section