For an input with the size of n, consider Alg1 to be a recursive algorithm structured as follows:

For n = 1, Alg1 requires 3 time units to return an answer.

For n > 1, Alg1 recurses 4 times on sub-problems each of size .

To combine the recursion results, Alg1 requires calculation.

a) write the recurrence T(n) for the running time of Alg1

b) Using the recursion tree analysis method, solve T(n) and compute the asymptotic running time of Alg1.

Please provide a detailed answer as I'm trying to understand how to solve these kinds of problems

Transcribed image text