## Description

CMSC 451 Homework 2

1. Given the following two functions:

f(n) = 3n

2 + 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

3

n

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)