1. Given the following two functions:
f(n) = 6n
3 + 4n
2 + 2
g(n) = 5n
2 + 9
Use L’Hopital’s rule and 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𝑛
2 + 10𝑛 + 5
3𝑛 log2 𝑛
4𝑛 + 10
3√𝑛
2
𝑛
𝑛
2 + 6𝑛
2 log2 𝑛
2𝑛
3 + 𝑛
2 + 6
4
n
log4 𝑛
3. Draw the recursion tree when n = 12, where n represents the length of the array, for the
following recursive method:
int sumSquares(int[] array, int first, int last) {
if (first == last)
return array[first] * array[first];
int mid = (first + last) / 2;
return sumSquares(array, first, mid) +
sumSquares(array, mid + 1, last);
}
Determine a formula that counts the numbers of nodes in the recursion tree.
What is the Big- for execution time?
Determine a formula that expresses the height of the tree.
What is the Big- for memory?
Write an iterative solution for this same problem and compare its efficiency with this
recursive solution.
4. Using the recursive method in problem 3 and assuming n is the length of the array.
Modify the recursion tree from the previous problem to show the amount of work on
each activation and the row sums.
Determine the initial conditions and recurrence equation.
Determine the critical exponent.
Apply the Little Master Theorem to solve that equation.
Explain whether this algorithm optimal.
