CMSC451 Homework 2 Solution

1. Given the following two functions:

• f(n) = 3n2 + 5
• g(n) = 53n + 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𝑛
• 𝑛3+5𝑛
• log2 𝑛
• 𝑛3 + 2𝑛2 + 1
• 3n
• log3 𝑛
• 𝑛2 + 5𝑛 + 10
• 𝑛 log2 𝑛
• 10𝑛 + 7
•
3. Draw the recursion tree when n = 8, where n represents the length of the array, for the following recursive method:
int sum(int[] array, int first, int last)
{ if (first == last) return array[first]; int mid = (first + last) / 2;
return sum(array, first, mid) + sum(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.
Grading Rubric
Problem Meets Does Not Meet
Problem 1 10 points 0 points

Used L'Hopital's rule to correctly determine limits (2) Did not use L'Hopital's rule to correctly determine limits (0)
Provided correct proof or disproof of Big-Theta relationship (4) Did not provide correct proof or disproof of Big-Theta relationship (0)
Provided correct proof or disproof of Big-Omega relationship (4) Did not provide correct proof or disproof of Big-Omega relationship (0)
Problem 2 10 points 0 points

Positioned exponential functions correctly (2) Did not position exponential functions correctly (0)
Positioned polynomial functions correctly (2) Did not position polynomial functions correctly (0)
Positioned constant functions correctly
(2) Did not position constant functions correctly (0)
Positioned logarithmic functions correctly (2) Did not position logarithmic functions correctly (0)
Positioned root functions correctly (2) Did not position root functions correctly (0)

Problem 3 10 points 0 points

Correctly drew recursion tree (2) Did not correctly draw recursion tree
(0)
Provided correct formula for number of nodes (2) Did not provide correct formula for number of nodes (0)
Provided correct Big-Theta for execution time (1) Did not provide correct Big-Theta for execution time (0)
Provided correct formula for tree heights (2) Did not provide correct formula for tree heights (0)
Provided correct Big-Theta for memory
(1) Did not provide correct Big-Theta for memory (0)
Wrote correct iterative solution (1) Did not write correct iterative solution
(0)
Provided correct comparison of efficiency of recursive and iterative solutions (1) Did not provide correct comparison of efficiency of recursive and iterative solutions (0)
Problem 4 10 points 0 points

Correctly drew modified recursion tree
(2) Did not correctly draw modified recursion tree (0)
Provided correct initial condition (1) Did not provide correct initial condition
(0)
Provided correct recurrence equation
(2) Did not provide correct recurrence equation (0)
Provided correct critical exponent (1) Did not provide correct critical exponent (0)
Correctly applied Little Master
Theorem to correctly solve recurrence equation (3) Did not correctly apply Little Master Theorem to correctly solve recurrence equation (0)
Provided correct explanation of whether algorithm is optimal (1) Did not provide correct explanation of whether algorithm is optimal (0)