Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 785

Normally, the loops in long-running algorithms are processing some kind of data.
Many algorithms run very quickly if the input dataset is small, so we generally worry
about the performance only for large datasets. For example, consider the following
set of loops that process an array of N elements:

for (N times) {
for (N times) {
statement1.
}
}

N 2

N 2 + 2N

for (N times) {
statement2.
statement3.
}

2N

When we analyze code like this, we often think about which line is most frequently
executed in the code. In programs with several sequential blocks of code that all relate
to some common value N (such as the size of an input dataset), the block raised to the
highest power of N usually dominates the overall runtime. In the preceding code, the
first N 2 loop executes its statement far more times than the second N loop executes its
two statements. For example, if N is 1,000, statement1 executes (1,000 * 1,000) or
1,000,000 times, while statement2 and statement3 each execute only 1,000 times.
When we perform algorithm analysis, we often ignore all but the most frequently
executed part of the code, because the runtime of this statement will outweigh the com-
bined runtimes of the other parts of the code. For example, we might refer to the pre-
ceding code as being “on the order of” N 2 , ignoring the extra 2 N statements altogether.
We'll revisit this idea later in the chapter.
One key concept to take away from this brief discussion of algorithm analysis is
how expensive it is to perform nested loops over large sets of input data. Algorithms
that make many nested passes over a very large dataset tend to perform poorly, so it's
important to come up with efficient algorithms that don't loop over data needlessly.
Now let's take a look at algorithm complexity in action, observing the runtimes of
some actual algorithms that can be used to solve a programming problem on a large
dataset.

Empirical Analysis
Consider the task of computing the range of numbers in an array. The range is the
difference between the lowest and highest numbers in the array. An initial solution
might use nested loops to examine every pair of elements in the array, computing
their difference and remembering the largest difference found:

max = 0.
for (each index i) {