Algorithm analysis - Data Structures and Problem Solving Using Java - page 203

The running time of statements inside a group of nested loops is the running
time of the statements (including tests in the innermost loop) multiplied by the sizes
of all the loops. The running time of a sequence of consecutive loops is equal to the
running time of the dominant loop. The time difference between a nested loop in
which both indices run from 1 to N and two consecutive loops that are not nested but
run over the same indices is the same as the space difference between a two-dimen-
sional array and two one-dimensional arrays. The first case is quadratic. The second
case is linear because N+N is 2 N , which is still . Occasionally, this simple rule
can overestimate the running time, but in most cases it does not. Even if it does, Big-
Oh does not guarantee an exact asymptotic answer—just an upper bound.

A worst-case
bound is a guaran-
tee over all inputs
of some size.

O ( N )

The analyses we have performed thus far involved use of a worst-case bound ,
which is a guarantee over all inputs of some size. Another form of analysis is the
average-case bound , in which the running time is measured as an average over all
of the possible inputs of size N . The average might differ from the worst case if,
for example, a conditional statement that depends on the particular input causes
an early exit from a loop. We discuss average-case bounds in more detail in Sec-
tion 5.8. For now, simply note that the fact that one algorithm has a better worst-
case bound than another algorithm implies nothing about their relative average-
case bounds. However, in many cases average-case and worst-case bounds are
closely correlated. When they are not, the bounds are treated separately.
The last Big-Oh item we examine is how the running time grows for each
type of curve, as illustrated in Figures 5.1 and 5.2. We want a more quantita-
tive answer to this question: If an algorithm takes time to solve a prob-
lem of size N , how long does it take to solve a larger problem? For instance,
how long does it take to solve a problem when there is 10 times as much
input? The answers are shown in Figure 5.10. However, we want to answer
the question without running the program and hope our analytical answers
will agree with the observed behavior.

In an average-case
bound , the running
time is measured
as an average over
all of the possible
inputs of size N .

T ( N )

figure 5.10
Observed running
times (in seconds) for
various maximum
contiguous
subsequence sum
algorithms

Figure 5.4 Figure 5.5 Figure 7.20 Figure 5.8

N O N ( ) ON ( ) O ( N log N ) O ( N )

10 0.000001 0.000000 0.000001 0.000000

100 0.000288 0.000019 0.000014 0.000005

1,000 0.223111 0.001630 0.000154 0.000053

10,000 218 0.133064 0.001630 0.000533

100,000 NA 13.17 0.017467 0.005571

1,000,000 NA NA 0.185363 0.056338