9.3 Additional Java Operators | 455Determining the complexities of different algorithms allows us to compare the work they re-
quire without having to program and execute them. For example, if you had an O(N^2 ) algorithm
and a linear algorithm that performed the same task, you probably would choose the linear
algorithm. We say probablybecause an O(N^2 ) algorithm actually may execute fewer steps than an
O(N) algorithm for small values of N. Recall that if the size factor Nis small, the constants and
lower-order terms in the complexity expression may be significant.
To see how this idea works, let’s look at an example. Suppose that Algorithm A is O(N^2 ) and
that Algorithm B is O(N). For large values of N, we would normally choose Algorithm B because it
requires less work than A. But suppose that in Algorithm B,S 0 = 1,000 and S 1 = 1,000. If N= 1, then
Algorithm B takes 2,000 steps to execute. Now suppose that for algorithm A,S 0 = 10,S 1 = 10, and
S 2 = 10. If N= 1, then Algorithm A takes only 30 steps to execute. The following table compares
the number of steps taken by these two algorithms for different values of N.
N Algorithm A Algorithm B
1 30 2,000
2 70 3,000
3 130 4,000
10 1,110 11,000
20 4,210 21,000
30 9,310 31,000
50 25,510 51,000
100 101,010 101,000
1,000 10,010,010 1,001,000
10,000 1,000,100,010 10,001,000From this table we can see that the O(N^2 ) Algorithm A is actually faster than the O(N) Algorithm
B, up to the point where Nequals 100. Beyond that point, Algorithm B becomes more efficient.
Thus, if we know that Nis always less than 100 in a particular problem, we would choose
Algorithm A. For example, if the size factor Nis the number of test scores on an exam and the
class size is limited to 30 students, Algorithm A would be more efficient. On the other hand, if N
is the number of scores at a university with 25,000 students, we would choose Algorithm B.
Constant, linear, quadratic, and cubic expressions are all examples of polynomialexpressions.
Algorithms whose complexity is characterized by such expressions are said to execute in polyno-
mial timeand form a broad class of algorithms that encompasses everything we’ve discussed so
far.
In addition to polynomial-time algorithms, we will encounter a logarithmic-time algorithm
in Chapter 11. There are also factorial [O(N!)], exponential [O(NN)], and hyperexponential [O(NNN)]
class algorithms, which can require vast amounts of time to execute and are beyond the scope
of this book. For now, the important point to remember is that different algorithms that solve
the same problem can vary significantly in the amount of work they do.