Java Reference
In-Depth Information
Some terminology will help with our descriptions of generic algorithm running
times.
Linear running time
means a running time of
T (N)
linear
running time
b
. A linear running
time is always an
O
(
N
) running time.
Quadratic running time
means a running time
with a highest term of
N
2
. A quadratic running time is always an
O
(
N
2
) running time.
We will also occasionally have logarithms in running-time formulas. Those normally
are given without any base, because changing the base is just a constant multiple. If you
see log
N
, think log base 2 of
N
, but it would not be wrong to think log base 10 of
N
.
Logarithms are very slow-growing functions. So, an
O
(log
N
) running time is very fast.
In many cases, our running-time estimates will be better than big-
O
estimates.
In particular, when we specify a linear running time, that is a tight upper bound and
you can think of the running time as being exactly
T (N)
=
aN
+
quadratic
running time
=
cN
, although the
c
is still
not specified.
Self-Test Exercises
=
+
19. Show that a running time
T
(
N
)
b
is an
O
(
N
) running time. (
Hint:
The
only issue is the plus
b
. Assume
N
is always at least 1.)
aN
20. Show that for any two bases
a
and
b
for logarithms, if
a
and
b
are both greater
than 1, then there is a constant
c
such that log
a
N
c
(log
b
N
). Thus, there is
no need to specify a base in
O
(log
N
). That is,
O
(log
a
N
) and
O
(log
b
N
) mean
the same thing.
…
Efficiency of Linked Lists
Now that we know about big-
O
notation, we can express the efficiency of various
methods for our linked data structures. As an example of analyzing the run-time efficiency
of an algorithm, consider the
find
method for the linked list class in Display 15.3.
This method starts at the head of the list and sequentially iterates through each node
to see whether it matches the target. If the linked list contains many nodes, then we
might get lucky if the target is found at the head of the list. In this case, the computer
had only to execute one step: Check the head of the list for the target. In the worst
case, the computer might have to search through all
n
nodes before finding (or not
finding) the target. In this case, the computer had to execute
n
steps. The worst case
will obviously take longer to execute than the best case. On average, we might expect
to search through about half of the list before finding the target. This would require
n
/2 steps. In our big-
O
notation, the find operation is
O
(
n
). However, the
addToStart
method requires linking only a new node to the head of the list. This runs in
O
(1) steps
(that is, a constant upper bound on the running time that is independent of the size of
the input).
