Java Reference
In-Depth Information
3.
Using Big Oh notation, indicate the time requirement of each of the following tasks in the worst case.
a.
Display all the integers in an array of integers.
b.
Display all the integers in a chain of linked nodes.
c.
Display the
n
th
integer in an array of integers.
d.
Compute the sum of the first
n
even integers in an array of integers.
4.
By using the definition of Big Oh, show that
a.
6
n
2
+
3 is O(
n
2
)
b.
n
2
+
17
n
+
1 is O(
n
2
)
c.
5
n
3
+
100
n
2
-
n
-
10 is O(
n
3
)
d.
3
n
2
+
2
n
is O(2
n
)
Algorithm X requires
n
2
+ 9
n
+ 5 operations, and Algorithm Y requires 5
n
2
operations. What can you conclude
about the time requirements for these algorithms when
n
is small and when
n
is large? Which is the faster algo-
rithm in these two cases?
5.
6.
Show that O(log
a
n
) = O(log
b
n
) for
a
,
b
> 1.
Hint
: log
a
n
= log
b
n
/ log
b
a
.
7.
If
f
(
n
) is O(g(
n
)) and
g
(
n
) is O(
h
(n)), use the definition of Big Oh to show that
f
(
n
) is O(
h
(
n
)).
8.
Segment 4.9 and the chapter summary showed the relationships among typical growth-rate functions. Indicate
where the following growth-rate functions belong in this ordering:
a.
n
2
log
n
b.
c.
n
2
/
log
n
d.
3
n
n
Show that 7
n
2
+ 5
n
is not O(
n
).
9.
10.
What is the Big Oh of the following computation?
int
sum = 0;
for
(
int
counter = n; counter > 0; counter = counter - 2)
sum = sum + counter;
11.
What is the Big Oh of the following computation?
int
sum = 0;
for
(
int
counter = 0; counter < n; counter = 2 * counter)
sum = sum + counter;
12.
Suppose that your implementation of a particular algorithm appears in Java as follows:
for
(
int
pass = 1; pass <= n; pass++)
{
for
(
int
index = 0; index < n; index++)
{
for
(
int
count = 1; count < 10; count++)
{
. . .
}
// end for
}
// end for
}
// end for
The algorithm involves an array of
n
items. The previous code shows the only repetition in the algorithm, but it
does not show the computations that occur within the loops. These computations, however, are independent of
n
.
What is the order of the algorithm?
