Asymptotic Order of growth

Our discussion of computational tractability has turned out to be intrinsically based on our ability to express the notion that an algorithm’s worst-case running time on inputs of size n grows at a rate that is at most proportional to some function f(n). The function f(n) then becomes a bound on the running time of the algorithm. We now discuss a framework for talking about this concept.

We will mainly express algorithms in the pseudo-code style that we used for the Gale-Shapley algorithm. At times we will need to become more formal, but this style of specifying algorithms will be completely adequate for most purposes. When we provide a bound on the running time of an algorithm, we will generally be counting the number of such pseudo-code steps that are executed; in this context, one step will consist of assigning a value to a variable, looking up an entry in an array, following a pointer, or performing an arithmetic operation on a fixed-size integer.an intermediate representation, and then into some further number of steps depending on the particular architecture being used to do the computing. So the most we can safely say is that as we look at different levels of computational abstraction, the notion of a “step” may grow or shrink by a constant factor— for example, if it takes 25 low-level machine instructions to perform one operation in our high-level language, then our algorithm that took at most 1.62n² + 3.5n + 8 steps can also be viewed as taking 40.5n² + 87.5n + 200 steps when we analyze it at a level that is closer to the actual hardware.

.O, , and 

For all these reasons, we want to express the growth rate of running times and other functions in a way that is insensitive to constant factors and loworder terms. In other words, we’d like to be able to take a running time like the one we discussed above, 1.62n² + 3.5n + 8, and say that it grows like n², up to constant factors. We now discuss a precise way to do this.

Asymptotic Upper Bounds Let T(n) be a function—say, the worst-case running time of a certain algorithm on an input of size n. (We will assume that all the functions we talk about here take nonnegative values.) Given another function f(n), we say that T(n) is O(f(n)) (read as “T(n) is order f(n)”) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n). We will also sometimes write this as T(n) = O(f(n)). More precisely, T(n) is O(f(n)) if there exist constants c > 0 and n0 ≥ 0 so that for all n ≥ n₀, we have T(n) ≤ c · f(n). In this case, we will say that T is asymptotically upperbounded by f. It is important to note that this definition requires a constant c to exist that works for all n; in particular, c cannot depend on n.

As an example of how this definition lets us express upper bounds on running times, consider an algorithm whose running time (as in the earlier discussion) has the form T(n) = pn² + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(n²). To see why, we notice that for all n ≥ 1, we have qn ≤ qn², and r ≤ rn². So we can write

T(n) = pn² + qn + r ≤ pn² + qn² + rn² = (p + q + r)n²

for all n ≥ 1. This inequality is exactly what the definition of O(·) requires: T(n) ≤ cn2, where c = p + q + r.

Note that O(·) expresses only an upper bound, not the exact growth rate of the function. For example, just as we claimed that the function T(n) = pn² + qn + r is O(n²), it’s also correct to say that it’s O(n³). Indeed, we just argued that T(n) ≤ (p + q + r)n², and since we also have n² ≤ n³, we can conclude that T(n) ≤ (p + q + r)n³ as the definition of O(n³) requires. The fact that a function can have many upper bounds is not just a trick of the notation; it shows up in the analysis of running times as well. There are cases where an algorithm has been proved to have running time O(n³); some years pass, people analyze the same algorithm more carefully, and they show that in fact its running time is O(n²). There was nothing wrong with the first result; it was a correct upper bound. It’s simply that it wasn’t the “tightest” possible running time.

Asymptotic Lower Bounds There is a complementary notation for lower bounds. Often when we analyze an algorithm—say we have just proven that its worst-case running time T(n) is O(n2)—we want to show that this upper bound is the best one possible. To do this, we want to express the notion that for arbitrarily large input sizes n, the function T(n)is at least a constant multiple of some specific function f(n). (In this example, f(n) happens to be n2.) Thus, we say that T(n) is (f(n)) (also written T(n) = (f(n))) if there exist constants  > 0 and n0 ≥ 0 so that for all n ≥ n0, we have T(n) ≥  · f(n). By analogy with O(·) notation, we will refer to T in this case as being asymptotically lowerbounded by f. Again, note that the constant  must be fixed, independent of n.

This definition works just like O(·), except that we are bounding the function T(n) from below, rather than from above. For example, returning to the function T(n) = pn2 + qn + r, where p, q, and r are positive constants,
let’s claim that T(n) = (n2). Whereas establishing the upper bound involved “inflating” the terms in T(n) until it looked like a constant times n2, now we need to do the opposite: we need to reduce the size of T(n) until it looks likea constant times n2. It is not hard to do this; for all n ≥ 0, we have

T(n) = pn² + qn + r ≥ pn²,

which meets what is required by the definition of (·) with  = p > 0. Just as we discussed the notion of “tighter” and “weaker” upper bounds, the same issue arises for lower bounds. For example, it is correct to say that
our function T(n) = pn2 + qn + r is (n), since T(n) ≥ pn2 ≥ pn.

Asymptotically Tight Bounds If we can show that a running time T(n) is both O(f(n)) and also (f(n)), then in a natural sense we’ve found the “right” bound: T(n) grows exactly like f(n) to within a constant factor. This, for
example, is the conclusion we can draw from the fact that T(n) = pn² + qn + r is both O(n²) and (n²).

Asymptotically tight bounds on worst-case running times are nice things to find, since they characterize the worst-case performance of an algorithm precisely up to constant factors. And as the definition of (·) shows, one can obtain such bounds by closing the gap between an upper bound and a lower bound. For example, sometimes you will read a (slightly informally phrased) sentence such as “An upper bound of O(n3) has been shown on the worst-case running time of the algorithm, but there is no example known on which the algorithm runs for more than (n2) steps.” This is implicitly an invitation to search for an asymptotically tight bound on the algorithm’s worst-case running time.

Sometimes one can also obtain an asymptotically tight bound directly by computing a limit as n goes to infinity. Essentially, if the ratio of functions f(n) and g(n) converges to a positive constant as n goes to infinity, then
f(n) = (g(n)).

Proof. We will use the fact that the limit exists and is positive to show that f(n) = O(g(n)) and f(n) = (g(n)), as required by the definition of (·).
Since

it follows from the definition of a limit that there is some n0 beyond which the ratio is always between 1/ 2c and 2c. Thus, f(n) ≤ 2cg(n) for all n ≥ n₀, which implies that f(n) = O(g(n)); and f(n) ≥ 1/ 2cg(n) for all n ≥ n₀, which impliesthat f(n) = (g(n)).

Properties of Asymptotic Growth Rates

Having seen the definitions of O, , and , it is useful to explore some of their basic properties.
Transitivity A first property is transitivity: if a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upperbounded by a function h, then f is asymptotically upper-bounded by h. A similar property holds for lower bounds. We write this more precisely as follows.

Proof. We’ll prove part (a) of this claim; the proof of part (b) is very similar. For (a), we’re given that for some constants c and n0, we have f(n) ≤ cg(n) for all n ≥ n₀. Also, for some (potentially different) constants c and n
0, we have g(n) ≤ c h(n) for all n ≥ n ₀. So consider any number n that is at least as large as both n₀ and n 0. We have f(n) ≤ cg(n) ≤ cc h(n), and so f(n) ≤ cc h(n) for all n ≥ max(n0, n ₀). This latter inequality is exactly what is required forshowing that f = O(h).

Combining parts (a) and (b) of (2.2), we can obtain a similar result for asymptotically tight bounds. Suppose we know that f = (g) and that g = (h). Then since f = O(g) and g = O(h), we know from part (a) that
f = O(h); since f = (g) and g = (h), we know from part (b) that f = (h). It follows that f = (h). Thus we have shown

(2.3) If f = (g) and g = (h), then f = (h).

Sums of Functions It is also useful to have results that quantify the effect of adding two functions. First, if we have an asymptotic upper bound that applies to each of two functions f and g, then it applies to their sum.

(2.4) Suppose that f and g are two functions such that for some other function h, we have f = O(h) and g = O(h). Then f + g = O(h).

Proof. We’re given that for some constants c and n₀, we have f(n) ≤ ch(n) for all n ≥ n₀. Also, for some (potentially different) constants c and n ₀, we have g(n) ≤ c h(n) for all n ≥ n ₀. So consider any number n that is at
least as large as both n₀ and n ₀. We have f(n) + g(n) ≤ ch(n) + c h(n). Thus f(n) + g(n) ≤ (c + c)h(n) for all n ≥ max(n₀, n ₀), which is exactly what is required for showing that f + g = O(h).

There is a generalization of this to sums of a fixed constant number of functions k, where k may be larger than two. The result can be stated precisely as follows; we omit the proof, since it is essentially the same as the proof of (2.4), adapted to sums consisting of k terms rather than just two.

(2.5) Let k be a fixed constant, and let f₁, f₂,..., f k and h be functions such that fi = O(h) for all i. Then f₁ + f₂ + ... + f_k = O(h).

There is also a consequence of (2.4) that covers the following kind of situation. It frequently happens that we’re analyzing an algorithm with two high-level parts, and it is easy to show that one of the two parts is slower than the other. We’d like to be able to say that the running time of the whole algorithm is asymptotically comparable to the running time of the slow part. Since the overall running time is a sum of two functions (the running times of the two parts), results on asymptotic bounds for sums of functions are directly relevant.

(2.6) Suppose that f and g are two functions (taking nonnegative values) such that g = O(f). Then f + g = (f). In other words, f is an asymptotically tight bound for the combined function f + g

Proof. Clearly f + g = (f), since for all n ≥ 0, we have f(n) + g(n) ≥ f(n). So to complete the proof, we need to show that f + g = O(f).

But this is a direct consequence of (2.4): we’re given the fact that g = O(f), and also f = O(f) holds for any function, so by (2.4) we have f + g = O(f).

This result also extends to the sum of any fixed, constant number of functions: the most rapidly growing among the functions is an asymptotically tight bound for the sum.

Asymptotic Bounds for Some Common Functions

There are a number of functions that come up repeatedly in the analysis of algorithms, and it is useful to consider the asymptotic properties of some of the most basic of these: polynomials, logarithms, and exponentials.

Polynomials Recall that a polynomial is a function that can be written in the form f(n) = a₀ + a₁n + a₂n² + ... + a_dn^d for some integer constant d > 0, where the final coefficient a_d is nonzero. This value d is called the degree of the polynomial. For example, the functions of the form pn^₂ + qn + r (with p = 0) that we considered earlier are polynomials of degree 2.

A basic fact about polynomials is that their asymptotic rate of growth is determined by their “high-order term”—the one that determines the degree. We state this more formally in the following claim. Since we are concerned here only with functions that take nonnegative values, we will restrict our attention to polynomials for which the high-order term has a positive coefficient a_d > 0.

1. (2.7) Let f be a polynomial of degree d, in which the coefficient a_d is positive. Then f = O(n^d).

Frequently Asked Questions