Complexity of the sum of two recursive function?

Question

I need to calculate the complexity of the following recursive function: T(n)=T(n/4)+3M(n/4)+11n-18 where M(n)=7M(n/4)+36n-52 for initial conditions as follows: T(1)=1 and M(1)=6

How can I calculate the complexity of T(n)? I know how to do it with a single recursive function but this time there are two recursive functions included in one formula and I don't know how to handle this problem?

There is a general formula based on the Master Theorem : Let M(n)=aM(n/b)+cn+d+fn^k and M(1)=e then the complexity of M(n) is calculated as follows:

--If a is not equal to b and f=0, then the solution of M(n) is: M(n)=(e+(bc/(a-b)) + d/a-1)n^log_ba - (bc/a-b).n+d/a-1

I want to use this general formula to calculate the complexity of T(n) above. Can someone help me on how to solve this problem please?

Answer 1

Notice that T references M, but M only references itself. This means that you could do a two-step process here:

1. Solve M(n).
2. Plug the solution into T(n), giving a recurrence for T(n) in terms of just itself, then solve T(n).

From your question it seems like you’re looking for an exact solution, though if you just care about asymptotically you can use the Master Theorem to get a solution as follows:

1. M(n) = Θ(n^{log₄ 7})
2. T(n) = T(n / 4) + 3M(n / 4) + O(n) = T(n / 4) + Θ(n^{log₄ 7}), which solves to Θ(n^{log₄ 7}).