[SOLVED] Homework 2

1. Given the following two functions:
 f(n) = 3n2 + 5
 g(n) = 53n + 9
Use limits to prove or disprove each of the following:
 f  (g)
 g  (f)
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.
 2𝑛
 𝑛3+5𝑛
 log2𝑛
 𝑛3+2𝑛2+1
 3n
 log3𝑛
 𝑛2+5𝑛+10
 𝑛 log2𝑛
 10𝑛+ 7
 √𝑛
Consider the following functions for problems 3 and 4.
int max(int[] array, int first, int last)
{
if (first == last)
return array[first];
else if (first + 1 == last)
return max(array[first], array[last]);
else
{
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)
return left;
return 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.