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

Our runtime predictions were roughly correct. As the size of the array doubles, the
runtime of this new range algorithm approximately doubles as well. The overall
runtime of this algorithm is much better; we can examine over a hundred million
integers in less than a second.
There are some important observations to take away from this exercise:

• Tweaking an algorithm's code often isn't as powerful an optimization as finding a

better algorithm.

• An algorithm's rate of growth, or the amount by which its runtime increases as the

input dataset grows, is the standard measure of the complexity of the algorithm.

Complexity Classes
We categorize rates of growth on the basis of their proportion to the input data size N.
We call these categories complexity classes or growth rates.

Complexity Class
A set of algorithms that have a similar relationship between input data size
and resource consumption.

The complexity class of a piece of code is determined by looking at the most fre-
quently executed line of code, determining the number of times it is executed, and
extracting the highest power of N. For example, if the most frequent line executes
(2 N 3 4 N ) times, the algorithm is in the “order N 3 ” complexity class, or O ( N 3 ) for

short. The shorthand notation with the capital O is called big-Oh notation and is used
commonly in algorithm analysis.
Here are some of the most common complexity classes, listed in order from slowest
to fastest growth (i.e., from lowest to highest complexity):

• Constant-time, or O (1), algorithms have runtimes that don't depend on input size.

Some examples of constant-time algorithms would be code to convert Fahrenheit
temperatures to Celsius or numerical functions such as Math.abs .

• Logarithmic , or O (log N ), algorithms typically divide a problem space in half repeat-

edly until the problem is solved. Binary search is an example of a logarithmic-time
algorithm.

• Linear, or O ( N ), algorithms have runtimes that are directly proportional to N

(i.e., roughly they double when N doubles). Many algorithms that process each
element of a data set are linear, such as algorithms that compute the count, sum,
average, maximum, or range of a list of numbers.

• Log-linear, or O ( N log N ), algorithms typically perform a combination of loga-

rithmic and linear operations, such as executing a logarithmic algorithm over
every element of a dataset of size N. Many efficient sorting algorithms, such as
merge sort (discussed later in this chapter), are log-linear.