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) = aN + b . A linear run-
ning time is always an O ( N ) running time. Quadratic running time means a run-
ning 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, since changing the base is just a con-
stant 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) = cN , although the c is still
not specified.
linear
running time
quadratic
running time
Self-Test Exercises
19. Show that a running time T ( N ) = aN + b is an O ( N ) running time. ( Hint: The
only issue is the plus b . Assume N is always at least 1.)
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 Dis-
play 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 only had to execute one step: Check the head of the list for the
target. In the worst case the compute 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 only linking a new node to the
head of the list. This runs in O (1) steps (that is, a constant upper bound on the run-
ning time that is independent of the size of the input).
Search WWH ::




Custom Search