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

additional restriction reduces this number. A precise calculation is
somewhat difficult to obtain and is performed in Theorem 5.1.
The most important part of Theorem 5.1 is not the proof, but rather the
result. There are two ways to evaluate the number of triplets. One is to evalu-
ate the sum . We could evaluate this sum inside out (see
Exercise 5.12). Instead, we will use an alternative.

ik j ≤≤

j

∑

N

∑

N

∑

1

i = 1 j = i ki =

The number of integer-ordered triplets ( i, j, k ) that satisfy 1 ≤≤ ≤ ≤ ik jN is

Theorem 5.1

.

NN 1 ( + ) ( N + 2 ) ⁄ 6

Proof

Place the following N + 2 balls in a box: N balls numbered 1 to N , one unnumbered
red ball, and one unnumbered blue ball. Remove three balls from the box. If a red ball
is drawn, number it as the lowest of the numbered balls drawn. If a blue ball is drawn,
number it as the highest of the numbered balls drawn. Notice that if we draw both a
red and blue ball, then the effect is to have three balls identically numbered. Order
the three balls. Each such order corresponds to a triplet solution to the equation in
Theorem 5.1. The number of possible orders is the number of distinct ways to draw
three balls without replacement from a collection of N + 2 balls. This is similar to the
problem of selecting three points from a group of N that we evaluated in Section 5.2,
so we immediately obtain the stated result.

The result of Theorem 5.1 is that the innermost for loop accounts for
cubic running time. The remaining work in the algorithm is inconsequential
because it is done, at most, once per iteration of the inner loop. Put another
way, the cost of lines 17 to 22 is inconsequential because that part of the code
is done only as often as the initialization of the inner for loop, rather than as
often as the repeated body of the inner for loop. Consequently, the algorithm
is ON 3 () .

The previous combinatorial argument allows us to obtain precise calcula-
tions on the number of iterations in the inner loop. For a Big-Oh calculation,
this is not really necessary; we need to know only that the leading term is
some constant times . Looking at the algorithm, we see a loop that is
potentially of size N inside a loop that is potentially of size N inside another
loop that is potentially of size N . This configuration tells us that the triple loop
has the potential for iterations. This potential is only about six
times higher than what our precise calculation of what actually occurs. Con-
stants are ignored anyway, so we can adopt the general rule that, when we
have nested loops, we should multiply the cost of the innermost statement by
the size of each loop in the nest to obtain an upper bound. In most cases, the

We do not need
precise calcula-
tions for a Big-Oh
estimate. In many
cases, we can use
the simple rule of
multiplying the size
of all the nested
loops. Note care-
fully that consecu-
tive loops do not
multiply.

N 3

NNN × ×