Java Reference
In-Depth Information
13.
Repeat the previous exercise, but replace 10 with
n
in the inner loop.
14.
What is the Big Oh of
method1
? Is there a best case and a worst case?
public static void
method1(
int
[] array,
int
n)
{
for
(
int
index = 0; index < n - 1; index++)
{
int
mark = privateMethod1(array, index, n - 1);
int
temp = array[index];
array[index] = array[mark];
array[mark] = temp;
}
// end for
}
// end method1
public static int
privateMethod1(
int
[] array,
int
first,
int
last)
{
int
min = array[first];
int
indexOfMin = first;
for
(
int
index = first + 1; index <= last; index++)
{
if
(array[index] < min)
{
min = array[index];
indexOfMin = index;
}
// end if
}
// end for
return
indexOfMin;
}
// end privateMethod1
15.
What is the Big Oh of
method2
? Is there a best case and a worst case?
public static void
method2(
int
[] array,
int
n)
{
for
(
int
index = 1; index <= n - 1; index++)
privateMethod2(array[index], array, 0, index - 1);
}
// end method2
public static void
privateMethod2(
int
entry,
int
[] array,
int
begin,
int
end)
{
int
index;
for
(index = end; (index >= begin) && (entry < array[index]); index--)
array[index + 1] = array[index];
array[index + 1] = entry;
}
// end privateMethod2
Consider two programs, A and B. Program A requires 1000
x
n
2
operations and Program B requires 2
n
operations.
For which values of
n
will Program A execute faster than Program B?
16.
17.
Consider four programs—A, B, C, and D—that have the following performances:
A: O(log
n
)
B: O(
n
)
C: O(
n
2
)
D: O(2
n
)
If each program requires 10 seconds to solve a problem of size 1000, estimate the time required by each program
for a problem of size 2000.