13 continued:

.

PLEASE ANSWER 9 THROUGH 13!!!!!!!!!!!! ---------------------------

9. Consider the recurrence T(n) = sqrt(2)T(n/2)+lg n.

a. Which case of the Master method can we use to solve the recurrence?

b. Wha does the recurrence evaluate to?

10. Consider the recurrence T(n)=16T(n/4)+n!.

a. Which case of the Master method can we use to solve the recurrence?

b. Wha does the recurrence evaluate to?

11. Consider the recurrence T(n)=nT(n/2)+lg n.This recurrence CANNOT be evaluated using the master method. WHY?

12. Consider the recurrence T(n)=2.2T(1.5n)+1. This recurrence CANNOT be evaluated using the master method. WHY?

13. Consider the recurrence T(n)= T(n-1)+lg(4n/3).

a. Using the iteration method, how many terms does the recurrence have?

b. Say T(n) = (f(n)). What is f(n)?

9. (4 points) Consider the recurrence T'(n) = V21 (n/2) +Ign. a (2 points) Which case of the Master Method can we use to solve the recurrence? A. Case 1 B. Case 2 C. Case 3 D. The Master Method will not work b. (2 points) What does the recurrence evaluate to? A. T(n) = (Ign) B. T(n)-(nlyn) C. T'(n) = e(n) D. none of the above 10. (4 points) Consider the recurrence T'(n) = 161'(n/4) +n!. a. (2 points) Which case of the Master Method can we use to solve the recurrence? A. Case 1 B. Case 2 C. Case 3 D. The Master Method will not work b. (2 points) What does the recurrence evaluate to? A. T(n) = e(n) B. T(n) (n lgn) C. T(n) = (n!) D. none of the above 11. (4 points) Consider the recurrence T' (n) = n'l'(n/2) + Ign. This recurrence cannot be evaluated using the Master Method. Why is that? A. The value of a is not a constant. B. The value of a can be less than 1. C. The value of b is less than or equal to 1. D. None of the above 12. (4 points) Consider the recurrence T'(n) = 2.21(1.50)+1. This recurrence cannot be evaluated using the Master Method. Why is that? A. The value of a is not an integer. B. The value of b is less than or equal to 1. c. f(n) is not a polynomial. D. None of the above 13. (10 points) Consider the recurrence T(n) = T(n-1) + 1g(4n/3). 4 a (5 points) Using the iteration method, how many terms does the recurrence have? A. Ign B. (4/3) C.n D. 4n/3 b. (5 points) Say T(n)= e(f(n)). What is S(n)? A. n B. Ign! C. nlgn D. nlgn