For each of the following recurrence relations, determine the runtime T(n) complexity. Use the Master Theorem to solve the recurrence relations if the recurrence relations can be solved using Master...

Correct and detailed answer is must for Upvote. Thank you!

Extracted text: For each of the following recurrence relations, determine the runtime T(n) complexity. Use the Master Theorem to solve the recurrence relations if the recurrence relations can be solved using Master Theorem, otherwise use expansion (or recursive substitution) to solve the recurrence relations. You must show all your working to justify your answer. Solution without clear justification or steps scores no mark. (a) T(n) = 4T (4) + n² + n (b) T(n) = 16T (A + n (c) T(n) = 16T (2) + n³ (d) T(n) = T(n – 1) + nª (e) T(n) = 2T () + n lg n