Description
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.
