Asymptotic Notation
Suppose we have two methods we wish to compare. We have determined that the running time for method A is 10n2 5 milliseconds to process n elements, while that for method B is 100n + 200 milliseconds. (We will discus how to arrive at these expressions in Section 7.3.) Which method should we prefer?
The answer depends on the value of n. As seen in Figure 7-3, for n = 6 method A is faster, but for n = 16 method B is much faster.
Figure 7-3. Method A is faster than method B for small values of n, but slower for large values.
(This item is displayed on page 187 in the print version)
We would prefer to say that one method is faster in general, rather than for some particular value of n. The time differences for small values of n are relatively insignificant. What really concerns us is the asymptotic behavior of the running-time functions: what happens as n becomes very large?
Figure 7-3 suggests that the running time for method A is larger than that for method B. If n is at least 12, B is faster.
Our intuition is correct in this example, but graphs can be deceiving. If we had plotted the graph only up to n = 6 (Figure 7-4), we might have concluded that method A is faster. To be confident in our statement about which method is faster for large values of n, we need a proof.
Figure 7-4. If the graph is plotted at a different scale, method A looks better.
(This item is displayed on page 188 in the print version)
Theorem: 10n2 5 > 100n + 200 for any value of n
Proof: For any n
The first and third inequalities follow because of the assumption that n
Actual running times will depend on a number of factors that don't really concern us, including the speed of the hardware, the quality of the compiler, and the skill of the programmer. We would prefer to make statements about the speed of an algorithm in general, rather than a particular implementation of it. This way, we don't have to redo our analysis if we change programming languages or buy a faster computer.
To keep our running-time expressions general, we allow them to contain unspecified constants. For example, we might find that the running time for algorithm A is an2 + b, while that for algorithm B is cn + d, with a, b, c, and d being unspecified constants that depend on factors such as the speed of the hardware.
The thought of doing proofs with all these unspecified constants lying around may be unnerving. Fortunately, there is a huge shortcut. Functions can be classified into orders. (Whenever we talk about orders, we assume that all of the functions involved map nonnegative integers onto nonnegative real numbers and are monotonically nondecreasingthat is, f(n + 1)
Some common orders are shown in Figure 7-5. We will give a formal definition of an order later in this section.
Order |
Nickname |
---|---|
Q(2n) |
|
Q(n3) |
cubic |
Q(n2) |
quadratic |
Q(n log n) |
|
Q(n) |
linear |
Q(log n) |
logarithmic |
Q(1) |
constant |
For any function f, Q(f) is pronounced "the order of f" or simply "order f." Each order is an infinitely large set of functions. The name of the order indicates one of the functions in that order. For example, n2 is one of the functions in Q(n2).
Among the orders in Figure 7-5, Q(2n) is the largest and Q(1) the smallest. This is what makes orders so useful: for sufficiently large n, a function is asymptotically larger than any function in a lower order. For example, for sufficiently large n, a function in Q(n log n) is asymptotically larger than any function in Q(n) and asymptotically smaller than any function in Q(n2).
Two rules go a long way toward identifying the order of a function:
- Multiplying or dividing a function by a positive constant doesn't change its order. For example, 3n2 and 0.2n2 are both in Q(n2).
- A function's order is not changed by adding or subtracting a function in a lower order. For example, 2n n + log n is in Q(2n).
Let's use these rules to find the order of f(n) = 5n3 + 3n2 4n + 11.
By the first rule, 5n3 is in Q(n3). Similarly, 3n2 is in Q(n2), 4n is in Q(n), and 11 is in Q(1). These are all lower orders, so we can ignore them by the second rule. Therefore, f(n) is in Q(n3). This was hardly any work at all, and we now know a great deal about how f(n) compares with other functions.
Let's look at some more examples. Given the running-time expressions in Figure 7-6, which algorithm should we use?
Algorithm |
Running Time |
---|---|
Column frobbing |
an2 b log n |
Row zorching |
cn + d |
The running time for the column frobbing algorithm is in Q(n2). The running time for the row zorching algorithm is in Q(n). Q(n) is a lower order, so we should choose row zorching.
Figure 7-7 presents two more running times to compare. Dynamic inversion takes time in Q(n3), but what about synchronized absquatulation?
Algorithm |
Running Time |
---|---|
Dynamic inversion |
an3 + bn2 + c |
Synchronized absquatulation |
|
Multiplying it out, we find that
Now we are back in familiar territory: Synchronized absquatulation takes time in Q(n2), so it is faster than dynamic inversion (for sufficiently large n).
A final challenge is given in Figure 7-8.
Algorithm |
Running Time |
---|---|
Cubic flensing |
an3 |
Factorial decortication |
n! |
Can we wrangle n! into some form we recognize?
Things don't look good. Notice, however, that this is at least
or
Factorial decortication takes time which is at least in Q(2n). Since cubic flensing is in the lower order Q(n3), we should choose cubic flensing.
Rather than proving that Q(n!) = Q(2n), which is not true, we proved something like Q(n!)
Analogy |
Notation |
Set |
---|---|---|
Q(f) f Q(g) and all higher orders |
||
Q(f) = Q(g) |
f Q(g) |
|
Q(f) f Q(g) and all lower orders |
Remember that functions in the same order can differ by a constant factor. Consequently, a function in O(g) might actually be larger than g. For example, 3n2
We can define these notations more formally. First, f
Similarly, f
f
What is the order of the expression 3n2 + 5n + n log n?
7.3
What is the order of the expression 5n log 5n?
7.4
What is the order of the expression (n + 3)(n 2)?
7.5
What is the order of the expression
7.6
What is the order of the volume of an n x n x n cube? What about the surface area? Answer the same questions for a cylinder of radius n and height n.
7.7
Use the identity
to prove that Q(log2 n), Q(log10 n), and Q(loge n) are the same order.
7.8
Prove that Q(max(f, g)) = Q(f + g). (Hint: Since max(f, g) = max(g, f) and f + g = g + f, you may assume without loss of generality that f(n) is larger than g(n) for sufficiently large values of n.)