1) Design an algorithm that determines the length of an array A. The only thing the algorithm can do to the array is attempt to obtain the value that is stored at a non-negative index i. Either the attempt will succeed, or it will result in an exception.

Your algorithm must be O(log n), where n is the (unknown) length of A.

There will be two distinct phases in your algorithm. In two or three succinct sentences, explain the key ideas behind the first phase.

2)In two or three succinct sentences, explain the key ideas behind the second phase of your algorithm from the previous question.

3) Consider the following algorithm for finding the largest element that occurs in an array A. To keep things simple, we'll assume that the length of A is a power of 2.

int largest (int[] A) { return largest(A, 0, A.length-1); } int largest (int[] A, int lo, int hi) { if (lo == hi) { return A[lo]; } else { int mid = (lo + hi) / 2; return Math.max(largest(A, lo, mid), largest(A, mid+1, hi)); } }

Derive the recurrence relation for this algorithm, which should be of the form

T(n) = a T(n/b) + O(nd)

a) What is a?

b) Referring to your recurrence from the previous question, what is b?

c) Referring to your recurrence from the previous question, what is d?

d) What upper bound does the Master Theorem put on your recurrence from the previous question? Use O() notation and do not include any blank spaces.