Java Reference
In-Depth Information
c
(6
N
+
5) nanoseconds. (We said
approximately
because we are making some simplify-
ing assumptions and therefore the result may not be the absolutely exact running
time.) This means that our running time of 6
N
+
5 is a very crude estimate. To get the
running time expressed in nanoseconds, you must multiply by some constant that
depends on the particular computer you are using. Our estimate of 6
N
+
5 is only
accurate to within a constant multiple.
Estimates on running time, such as the one we just went through, are normally
expressed in something called
big-O notation
. (The
O
is the letter “Oh,” not the digit
zero.) Suppose we estimate the running time to be, say, 6
N
+
5 operations, and sup-
pose we know that no matter what the exact running time of each different operation
may turn out to be, there will always be some constant factor
c
such that the real run-
ning time is less than or equal to
c
(6
N
+
5). Under these circumstances, we say that
the code (or program or algorithm) runs in time
O
(6
N
+
5). This is usually read as
“big-
O
of 6
N
+
5.” We need not know what the constant
c
will be. In fact, it will
undoubtedly be different for different computers, but we must know that there is one
such
c
for any reasonable computer system. If the computer is very fast, the
c
might be
less than 1—say, 0.001. If the computer is very slow, the
c
might be very large—say,
1,000. Moreover, since changing the units (say from nanosecond to second) only
involves a constant multiple, there is no need to give any units of time.
Be sure to notice that a big-
O
estimate is an upper-bound estimate. We always
approximate by taking numbers on the high side rather than the low side of the true
count. Also notice that when performing a big-
O
estimate, we need not determine an
exact count of the number of operations performed. We only need an estimate that is
correct up to a constant multiple. If our estimate is twice as large as the true number,
that is good enough.
An order-of-magnitude estimate, such as the previous 6
N
+
5, contains a parameter
for the size of the task solved by the algorithm (or program or piece of code). In our sam-
ple case, this parameter
N
was the number of array elements to be searched. Not surpris-
ingly, it takes longer to search a larger number of array elements than it does to search a
smaller number of array elements. Big-
O
running-time estimates are always expressed as a
function of the size of the problem. In this chapter, all our algorithms will involve a range
of values in some container. In all cases
N
will be the number of elements in that range.
The following is an alternative, pragmatic way to think about big-
O
estimates:
big-O
notation
Only look at the term with the highest exponent and
do not pay attention to constant multiples.
For example, all of the following are
O
(
N
2
):
N
2
+
2
N
+
1, 3
N
2
+
7, 100
N
2
+
N
All of the following are
O
(
N
3
):
N
3
+
5
N
2
+
N
+
1, 8
N
3
+
7, 100
N
3
+
4
N
+
1
