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 73, for n = 6 method A is faster, but for n = 16 method B is much faster.
Figure 73. 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 runningtime functions: what happens as n becomes very large?
Figure 73 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 74), 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 74. 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 images/U2265.jpg border=0> 12.
Proof: For any n images/U2265.jpg border=0> 12:
The first and third inequalities follow because of the assumption that n images/U2265.jpg border=0> 12. This completes the proof.
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 runningtime 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) n). An algorithm for which the runningtime function did not fit into this category would be fairly strange.)
Some common orders are shown in Figure 75. 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 75, 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:
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 runningtime expressions in Figure 76, 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 77 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 78.
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!) Q(f) is the set of functions which grow like f, then W(f) is the set of functions which grow like f or much more quickly. In set theory terms, it is the union of Q(f) and all higher orders. We proved that n! is in W(2n). Various related notations are summarized in Figure 79.
Analogy 
Notation 
Set 

Q(f) f Q(g) and all higher orders 

Q(f) = Q(g) 
f Q(g) 

Q(f) f O( 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 O(n2 is larger than n2 (by a factor of 3).
We can define these notations more formally. First, f O(c > 0, there is some n0 0 such that n) < cg(n) for any n We've seen n0 before; that's just a threshold so that only large values of n are considered. (In Figure 73, n0 was 12.) The constant c is there so that multiplying either function by a constant won't have any effect. Put another way, the definition says that f O(Q(g) is larger than f for sufficiently large n.
Similarly, f 0 such that n) > cg(n) for any n Combining these, we get the formal definition of an order:
f O(f O(asymptotic upper bound on f. Showing that f Q(kn) are called exponential orders. For k > 0, the orders Q(nk) are called polynomial orders. These fit into the order hierarchy right where we would expect. For example, n5 O(3in 7.2
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.)
Part I: ObjectOriented Programming
Encapsulation
Polymorphism
Inheritance
Part II: Linear Structures
Stacks and Queues
ArrayBased Structures
Linked Structures
Part III: Algorithms
Analysis of Algorithms
Searching and Sorting
Recursion
Part IV: Trees and Sets
Trees
Sets
Part V: Advanced Topics
Advanced Linear Structures
Strings
Advanced Trees
Graphs
Memory Management
Out to the Disk
Part VI: Appendices
A. Review of Java
B. Unified Modeling Language
C. Summation Formulae
D. Further Reading
Index