Java Reference
In-Depth Information
are making some simplifying 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
big-
O
notation
+
5 operations,
and suppose 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 running 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, because changing the units (say from nanosecond to second) involves
only 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 need only 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
sample case, this parameter
N
was the number of array elements to be searched. Not
surprisingly, 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:
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
3
N
2
100
N
2
N
+
2
N
+
1,
+
7,
+
All of the following are
O
(
N
3
):
N
3
5
N
2
8
N
3
100
N
3
1
+
+
N
+
1,
+
7,
+
4
N
+
