4. a. Use the Master Theorem to evaluate the growth-rate of the following recurrence relations: i....

 

Transcribed Image Text:

4. a. Use the Master Theorem to evaluate the growth-rate of the following recurrence relations: i. T(n) = 16 T(n/4) + n ii. T(n) = 3 T(n/9) + n Hint: You may use the fact that log y = log10 y/ log10 x. b. Consider the following recurrence relation T(1) T(n) 4 T([n/2])+n for all n > 1. Prove, by induction on the input n, that T(n) 2n = 1 for all n 1. Hint: You may use the fact that T([n/2]) T(n/2). [4 marks] [7 marks] 4. a. Use the Master Theorem to evaluate the growth-rate of the following recurrence relations: i. T(n) = 16 T(n/4) + n ii. T(n) = 3 T(n/9) + n Hint: You may use the fact that log y = log10 y/ log10 x. b. Consider the following recurrence relation T(1) T(n) 4 T([n/2])+n for all n > 1. Prove, by induction on the input n, that T(n) 2n = 1 for all n 1. Hint: You may use the fact that T([n/2]) T(n/2). [4 marks] [7 marks]