CMSC 451 UMCP Recursive Function Sum Project

CMSC 451 Homework 21. 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𝑛
log 2 𝑛
𝑛3 + 2𝑛2 + 1
3n
log 3 𝑛
𝑛2 + 5𝑛 + 10
𝑛 log 2 𝑛
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
Problem 1
Problem 2
Meets
10 points
Does Not Meet
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)
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)
10 points
Correctly drew recursion tree (2)
0 points
Did not correctly draw recursion tree
(0)
Provided correct formula for number of Did not provide correct formula for
nodes (2)
number of nodes (0)
Problem 3
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)
10 points
Problem 4
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)
Provided correct explanation of
whether algorithm is optimal (1)
Did not correctly apply Little Master
Theorem to correctly solve recurrence
equation (0)
Did not provide correct explanation of
whether algorithm is optimal (0)