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.
 
Search WWH ::




Custom Search