1. Given the following two functions:
f(n) = 3n2 + 5
g(n) = 53n + 9
Use limits to prove or disprove each of the following:
2. Rank the following functions from lowest asymptotic order to highest. List any two or more that are of the same order on the same line.
Consider the following functions for problems 3 and 4.
int max(int array, int first, int last)
if (first == last)
else if (first + 1 == last)
return max(array[first], array[last]);
int mid = (first + last) / 2;
return max(max(array, first, mid), max(array, mid + 1, last));
int max(int left, int right)
if (left > right)
3. Write the recurrence equation that expresses the execution time cost for the above algorithm. Draw the recursion tree assuming that n= 8.
4. Determine the critical exponent for the recurrence equation in problem 3. Apply the Little Master Theorem to solve that equation. Is this algorithm optimal? Explain.