Solve the following recurrence equation (tight upper and lower bounds!)

Piecewise Function

T(n) = 1 if n

T(n) = 2T(n/2) + 23 otherwise

a) Using the master theorem. Make sure to explain which case applies as why.

b) Using the recursion tree method. Do not use asymptotic notation for the depth of the recursion tree; use exact upper and lower bounds instead.

c) Using the substitution method. Make sure to show that the boundary conditions hold as well; choose the constraints c and n₀ appropriately.