2. Determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution...

 

Transcribed Image Text:

2. Determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using a recursion tree. You may not use the Master Theorem as justification of your answer. Simplify and express your answer as O(n) or (nk log2 n) whenever possible. If the algorithm is exponential just give exponential lower bounds. Assume T(1) c'. a) T(n) = 3T(n/3) + cn b) T(n) = 4T(n/2) + cn 2. Determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using a recursion tree. You may not use the Master Theorem as justification of your answer. Simplify and express your answer as O(n) or (nk log2 n) whenever possible. If the algorithm is exponential just give exponential lower bounds. Assume T(1) c'. a) T(n) = 3T(n/3) + cn b) T(n) = 4T(n/2) + cn