Erik's answers to the 331 Review questions

1.

for( i=0; i<n; i++) 
    for( j=n; j>1; j/=2) 
	A[i][j] = 0;
The inner j loop will run with the values n, n/2, n/4, n/8, ... in total lg n times.
The outter i loop runs n times. Since the loops are independent, but nested, multiply the two to get n lg n. For this question, the best case is the same as the worst case.
(note: it is assumed that lg = lg2).

2.

for( i=0; i<n2; i++)
    for( j=0; j<i; j++)
	A[i][j]++;
The inner loop runs a total of i times. To solve this one, we set up some summations to help us:

The first summation is the outer loop. i ranges from 0 to n2. The second summation is the inner loop. j ranges from 0 to i. The second summation simply resolves to i ( 1 + 1 + 1 + 1 + ... i times):

If the upper limit was n this is an easy summation, the answer would be n(n+1)/2. The n2 doesn't complicate things any, just substitute it in: n2(n2+1)/2. The answer is roughly O(n4).

3.

for( i=0; i<n; i++) {
   if( A[i]%2 ) {
	for( j=0; j<n; j++)
	   B[i][j] = 17;
   }
}
Because we have a conditional nested inside one of the loops, we're going to have best and worst case scenarios. The %2 checks if a number is even or odd. If any A[i] is odd, then the j loop is executed. It follows that the best case is if all A[i] are even, we only have O(n), which is the best case. If all A[i] are odd, then the j loop is executed, so we have O(n2).

4.

for( i=0; i<n; i++) A[i] = 0;
for( j=0; j<n2; j++) B[j] = 0;
for( k=n; k>1; k++) C[k] = 0;
By inspection, the first loop is O( n ), the second loop is O(n2), the third loop is O( lg n ).
The O(n2) domniates both O( n ) and O( lg n ), so overall, the whole program is O(n2).

5.

Give an efficient way to search for an element in a sorted array containing n elements. What is this search techinique called, and what is the big O running time?
Since the list is already sorted, we can paritition it into two, and base our search on one of the halves, based on the middle element. If our key is greater than the middle element, we can automatically discard the lower half, and vice-verca. This is a binary search, which is O( lg n ).

6.

Given an unsorted array of n elements, how many comparisons are needed to find the largest valued sorted in the array?
n-1 comparisons are needed: Take the first element to be the largest, then compare it against all the other elements (n-1 of them), picking the larger one.

7.

Given an unsorted array of n elements, how many comparisons are needed to find the second largest element?
(1) Take the first two elements, and choose the larger one.
(2*(n-2))For the remaining elements, compare each one to the two, picking the larger of each.
In total, we have 2n + 1 comparions, which is O( n ).

8.

How does insertion sort work?
See sorting notes for notes and an example.
main page | page 2