1. Given the following recurrence:

T(n) = { 7 if n<=3

5T(n/3)+n otherwise }

Draw the first two levels of the recursion tree, and the leaf level of the tree.

2. For each function f(n) and time t in the table below, find the largest size n of a problem

that can be solved in time t. Assume that the algorithm to solve the problem takes f(n)

microseconds. For large entries, an estimate is acceptable. For one of the rows, you will

not be able to solve it analytically, you may need to write a small program. Show your

work. Note: all the logs are with the Base 2 Algorithm of n

1000 log n for: (1 second, 1 minute, 1 hour, 1 day, 1 month, and 1 year)

100 n for: (1 second, 1 minute, 1 hour, 1 day, 1 month, and 1 year)

100n log n for: (1 second, 1 minute, 1 hour, 1 day, 1 month, and 1 year)

n^3 for: (1 second, 1 minute, 1 hour, 1 day, 1 month, and 1 year)

(1/10) * 2^n for: (1 second, 1 minute, 1 hour, 1 day, 1 month, and 1 year)

3. Prove or disprove:

n log (base 10 of n) theta (n log base 2 of n).

4. Let T(n) be the running time of the following procedure on input n. Find a function f(n) such that T(n) theta (f(n)), and justify your answer.

Procedure triple(integer n):

For i from 1 to n do

For j from 3 to n/2 do

For k from j to j+100 do

If j-k is even

Then x = x+1;

Else x = 2*x;

5. Let T(n) be the running time of the following procedure on input n. Find a function f(n) such that T(n) theta (f(n)), and justify your answer.

Procedure double (integer n):

For i from 1 to n do

For j from i +1 to n do

x = x + 1;