Java Reference
In-Depth Information
Another O(
n
2
) algorithm
FIGURE 4-8
for
i = 1
to
n
{
for
j = 1
to
n
sum = sum + 1
}
...
i =
1
...
i =
2
i =
3
...
.
.
.
n
) = O(
n
2
)
i = n
...
O(
n
1
2
3
n
Question 5
Using Big Oh notation, what is the order of the following computation's time
requirement?
for
i = 1
to
n
{
for
j = 1
to
5
sum = sum + 1
}
4.21
Let's get a feel for the growth-rate functions in Figure 4-4. As we mentioned, the time requirement
for an O(1) algorithm is independent of the problem size
n
. We can apply such an algorithm to
larger and larger problems without affecting the execution time. This situation is ideal, but not typical.
For other orders, what happens if we double the problem size? The time requirement for an
O(log
n
) algorithm will change, but not by much. An O(
n
) algorithm will need twice the time, an
O(
n
2
) algorithm will need four times the time, and an O(
n
3
) algorithm will need eight times the
time. Doubling the problem size for an O(
2
n
) algorithm squares the time requirement. Figure 4-9
tabulates these observations.
Question 6
Suppose that you can solve a problem of a certain size on a given computer in
time
t
by using an O(
n
) algorithm. If you double the size of the problem, how fast must your
computer be to solve the problem in the same time?
Question 7
Repeat the previous question, but instead use an O(
n
2
) algorithm.
