COMP2011 Tutorial Solutions 3, Week 4 COMP2011 Tutorial Solutions 3, Week 4 Algorithms Any questions about Assignment 1. Give a tight "Big-Oh" characterization, in terms of n, of the running time of each method in the following class:
public int Ex1( int A[] ) {
// compute sum of elements of A
int s = 0;
for( int i=0; i < A.length; i++ ) {
s += A[i];
}
return( s );
}
public void Ex2( int A[], int B[] ) {
// store the prefix sums of A into B
int i,j,s;
for( i=0; i < A.length; i++ ) {
s = 0;
for( j=0; j <= i; j++ ) {
s += A[j];
}
B[i] = s;
}
}
public void Ex3( int A[], int B[] ) {
// store the prefix sums of A into B
int i,s;
s = 0;
for( i=0; i < A.length; i++ ) {
s += A[i];
B[i] = s;
}
}
public void Ex4( int A[], int B[] ) {
// store the prefix sums of prefix sums of A into B
int i,j,k,s;
for( i=0; i < A.length; i++ ) {
s = 0;
for( j=0; j <= i; j++ ) {
for( k=0; k <= j; k++ ) {
s += A[k];
}
}
B[i] = s;
}
}
Can Ex4() be re-written so that it runs faster? How much faster? Ex1() is linear, i.e. O(n) Ex2() is quadtratic, i.e. O(n2) Ex3() is linear, i.e. O(n) Ex4() is cubic, i.e. O(n3) Ex4() can be re-written to run in linear time, in two different ways:
public static void Ex4a( int A[], int B[] ) {
// store the prefix sums of prefix sums of A into B
int i,s,t;
s = t = 0;
for( i=0; i < A.length; i++ ) {
s += A[i];
t += s;
B[i] = t;
}
}
public static void Ex4b( int A[], int B[] ) {
// store the prefix sums of prefix sums of A into B
Ex3( A, B );
Ex3( B, B );
}
R-3.2: The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n >= n0. This is true so long as 4logn <= n, i.e. n >= 16, so n0=16. What is the definition of f(n) being O(g(n))? There exist numbers c and n0 such that f(n) <= c.g(n), for n >= n0 R-3.12: Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)+e(n) is O(f(n)+g(n))
d(n) is O(f(n)), and e(n) is O(g(n))
-> d(n) <= K f(n) for n >= N, and e(n) <= L g(n) for n >= M
-> d(n) + e(n) <= K f(n) + L g(n)
<= (K + L)(f(n) + g(n)), for n >= max(N,M)
R-3.16: Show that O(max{f(n),g(n)}) = O(f(n)+g(n))
d(n) <= K max{f(n),g(n)} -> d(n) <= K (f(n) + g(n))
Conversely,
d(n) <= K (f(n) + g(n)) -> d(n) <= (2K) max{f(n),g(n)}
C-3.4: Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons. First compare each consecutive pair of numbers, collecting the lower of each pair into one group and the higher into another group. This step will take n/2 comparisons. Then use n/2 comparisons to find the smallest of the low numbers, and n/2 comparisons to find the largest of the high numbers (making 3n/2 comparisons altogether). If properly written, the two steps can be done at the same time, with no need to actually copy the numbers from one place to another. Author: Alan Blair
