## COMP2011 Tutorial Exercises 3, Week 4

#### Algorithms

1. Any questions about Assignment 1.

2. 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?

3. 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.

4. What is the definition of f(n) being O(g(n))?
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))
R-3.16: Show that O(max{f(n),g(n)}) = O(f(n)+g(n))

5. C-3.4: Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons.

6. Any items remaining from previous weeks.