Do problems (i), (ii) and (iii) below.

i. Carryoutthisalgorithmonthe8elementlistL=1249615273.
Show your work. (It is sufficient here to just show the tree representing the computation.)

State exactly how many comparisons are done on your example run.
ii. Define M(n) = the number of comparisons done by DandC-MIN-AND-MAX(L) where n =

|L|.

iii. Now derive a closed form for your recurrence expressing M(n) as a function of n.
(Note: A closed form means to write M(n)≤ …., where … is an explicit function of n but does not contain M. See pages 210-211 of the textbook where this is explained, especially the paragraphs in the middle of page 211.)

1

Write a recurrence relation for M expressing M(n) in terms of M(k) where k is smaller than n.

2. For all the parts i. ii. and iii. below you should briefly justify your work.

i. Consider the recurrence relation T(n) = 3T(n/3)+2, with n a power of 3 (n = 3k) and the base case T(1) = 0.

Compute the first 5 values of T(n): T(3), T(9), T(27), T(81), T(243).

Compute a closed form for T, and give the rate of growth of T (that is, does T have polynomial growth or O(n log n) growth or exponential growth or …)?

ii. Consider the recurrence relation R(n) = an = an−2 + an−1 + 3 where base cases are R(1) = a1 =1andR(2)=a2 =2.

Compute the first 6 values of R(n) past the base cases: R(3), R(4), …, R(8). Show your work.

Compute a closed form for R, or if too hard, give the rate of growth of R (that is, does R have polynomial growth or exponential growth or ….)?

iii. Consider the recurrence relation S(n) = an = 4an−1 − 2 where S(0)= a0 = 2. Compute the first 6 values of S(n): S(1), S(2), S(3), …, S(6) after S(0). Show your work.

Compute a closed form for S, and give the rate of growth of S (that is, is does S have polynomial growth or exponential growth or….)?

DETAILED ASSIGNMENT

20210401165448hw6_330_final4