Consider the following mysterious recursive algorithm:

function f(list, low, high, size)

if (size == 1)

return list[low];

else

return f(list, low, high-1, size-1) + f(list, low+1, high, size-1);

a.) Write the reccurance relation T that counts the number of recursice calls to the function f when called initially with a list size n. ( T(n)=2T(n-1)+2, T(1)=0 )

b.) Give the closed form solution and be sure to show all work.

c.) Prove your solution is correct by using an induction proof.

d.) What is the order of growth for this function f ?

2. The following algorithm sorts an array of size n which contatins only valuesw which are either 0 or 1.

function zeroOneSort(L,n){

i=0;

for(j=0;j

if(L[j] == 0) {

temp[i] = L[j];

i++;

}

}

for(j=0; j

if(L[j] == 1){

temp[i] = L[j];

i++;

}

}

copyArray(temp, L); // copy array temp into array L

}

a.) How many comparisons and how many moves in the arrays are done by this algorithm?

b.) Why does this not contradict the lower bound for sorting?