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

Did You Know?

Timing Code and the Epoch
Java's method System.currentTimeMillis returns the number of milliseconds
that have passed since 12:00 AM on January 1, 1970. This method can be used to
measure the runtime of an algorithm. Over one trillion milliseconds have passed
since the indicated time, so the value is too large to store in a simple int value.
The milliseconds are instead returned as a value of type long , which is a primi-
tive type that's similar to int but that is capable of holding much larger values. A
long can store any number up to 9,223,372,036,854,775,807, or roughly 2 63 .

The following lines of code show how a piece of code can be timed:

long startTime = System.currentTimeMillis();
<code to be timed>
long endTime = System.currentTimeMillis();
System.out.println("Elapsed time (ms): " + (endTime - startTime));

The choice of January 1, 1970 as the point of reference for system times is an
example of an epoch, or an instant chosen as the origin of a particular time scale.
This particular epoch was chosen because it matches the epochs of many popular
operating systems, including Unix.

For historical reasons, many older Unix operating systems store the time that
has passed since the epoch as a 32-bit integer value. However, unspecified prob-
lems may occur when this number exceeds its capacity, which is not necessarily a
rare event. The clocks of some Unix systems will overflow on January 19, 2038,
creating a Year 2038 problem similar to the famous Year 2000 (Y2K) problem.

Quadratic, or O ( N 2 ), algorithms have runtimes that are proportional to the square
of the input size. This means that quadratic algorithms' runtimes roughly quadru-
ple when N doubles. The initial versions of the range algorithm developed in the
previous section were quadratic algorithms.

•

Cubic, or O ( N 3 ), algorithms have runtimes that are proportional to the cube of the
input size. Such algorithms often make triply nested passes over the input data.
Code to multiply two N

•

N matrices or to count the number of colinear trios of
points in a large Point array would be examples of cubic algorithms.

• Exponential, or O (2 N ), algorithms have runtimes that are proportional to 2 raised

to the power of the input size. This means that if the input size increases by just
one, the algorithm will take roughly twice as long to execute. One example would
be code to print the “power set” of a dataset, which is the set of all possible sub-
sets of the data. Exponential algorithms are so slow that they should be executed
only on very small input datasets.