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

As you progress in this textbook, you're writing increasingly complex programs.
You're also seeing that there are often many ways to solve the same problem. How do
you compare different solutions to the same problem to see which is better?
We desire algorithms that solve problems quickly or with high efficiency. The
technical term that refers to algorithms' runtime is complexity . An algorithm with
higher complexity uses more time or resources to solve a problem.

Complexity
A measure of the computing resources that are used by a piece of code,
such as time, memory, or disk space.

Usually when we talk about the efficiency of a program we are talking about
how long the program takes to run, or its time complexity. The time complexity for a
program to be “fast enough” depends on the task. A program running on a modern
computer that requires five minutes to look up a dictionary word is probably too
slow. An algorithm that renders a complex three-dimensional movie scene in five
minutes is probably very fast.
One way to determine an algorithm's approximate time complexity is to program
it, run the program, and measure how long it takes to run. This is sometimes called an
empirical analysis of the algorithm. For example, consider two algorithms to search
an array: one that sequentially searches for the desired target element, and one that
first sorts the array and then performs a binary search on the sorted array. You could
empirically analyze the algorithms by writing both as programs, running them on the
same input, and timing them.
But empirically analyzing an algorithm isn't a very reliable measure, because on a
different computer with a different processor speed and more or less memory the pro-
gram might not take the same amount of time. Also, in order to empirically test an
algorithm, you must write it and time it, which can be a chore.
A more neutral way to measure a program's performance is to examine its code or
pseudocode and roughly count the number of statements that are executed. This is a
form of algorithm analysis, the practice of applying techniques to mathematically
approximate the performance of various computing algorithms. Algorithm analysis is
an important tool in computer science. One of the fundamental principles of science
in general is that we can make predictions and hypotheses using formal models,
which we can then test by experimentation.
Not all statements require the same amount of time to execute. For example, a
CPU can handle addition faster than multiplication, and a method call generally takes
more time than a statement that evaluates the Boolean test of an if/else statement.
But for the purposes of simplification, let's assume that the following actions require
an equal and fixed amount of time to execute:

• Variable declarations and assignments

• Evaluating mathematical and logical expressions