(a) Draw the recursion tree for T(n) when n = 6 where T(n) = T(n/2) + T(n 1) if n is odd and n 3 and T(n) = T(n 1) + T(n 2) + 1 if n is even. Assume T(1) = 1 and T(0) = 0.

(b) Solve the recurrence: T(n) = T(n/4) + T(n/3) + O(n) for n > 12. You may assume n is a power of 12 and that T(n) = (1) for n 12. Does the master theorem apply to this recurrence? Justify your answer

Please provide with good explanation with draw the recursion tree