Java Reference
In-Depth Information
4.19
Algorithm B in Figure 4-1 contains nested loops, as follows:
for
i = 1
to
n
{
for
j = 1
to
i
sum = sum + 1
}
When loops are nested, you examine the innermost loop first. Here, the body of the inner loop
requires a constant amount of execution time, and so it is O(1). If we again represent that time with
an icon, a row of
i
icons represents the time requirement for the inner loop. Since the inner loop is
the body of the outer loop, it executes
n
times. Figure 4-7 illustrates the time requirement for these
nested loops, which is proportional to 1
+
2
+
. . .
+
n
. Question 1 asked you to show that
1
+
2
+
. . .
+
n
=
n
(
n
+
1)
/
2
which is
n
2
/ 2 +
n
/ 2. Thus, the computation is O(
n
2
).
An O(
n
2
) algorithm
FIGURE 4-7
for
i = 1
to
n
{
for
j = 1
to
i
sum = sum + 1
}
i =
1
i =
2
i =
3
.
.
.
i = n
...
O(1
2
...
n
) = O(
n
2
)
1
2
3
n
4.20
The body of the inner loop in the previous segment executes a variable number of times that
depends on the outer loop. Suppose we change the inner loop so that it executes the same number
of times for each repetition of the outer loop, as follows:
for
i = 1
to
n
{
for
j = 1
to
n
sum = sum + 1
}
Figure 4-8 illustrates these nested loops and shows that the computation is O(
n
2
).
