I am studying the Master Theorem, but there is a case in which I have no knowledge on how one should proceed. If it's given:

$T_1(n)= 1$ if n=1

$T_1(n)= 4T_1(\frac n2) + \sqrt{3n}+1$ otherwise.

For this case $T_1(n) \in \Theta(n^2)$

We then have:

$T_2(n)= 1$ if n=1

$T_2(n)= 14T_2(\frac n4)+ T_1(n)=14T_2(\frac n4)+4T_1(\frac n2) + \sqrt{3n}+1$ otherwise.

If I'd like to define a,b,c how do I proceed?

Is the number of nodes in a layer for the recurrence tree 18 ?

I am unfamiliar with how one proceeds in this case.

  • 2
    $\begingroup$ From the first part you already know $T_1(n) = \theta(n^2)$ thus: $T_2(n) = 14T_2(n/4) + \theta(n^2)$. Now you can apply the Master Theorem. $\endgroup$
    – plshelp
    May 2 at 0:22
  • $\begingroup$ @plshelp You should post that as an answer. $\endgroup$
    – Nathaniel
    May 2 at 0:43
  • $\begingroup$ @plshelp That's what I did but there is a contradiction when I try to find the asymptotic behavior for this $\endgroup$
    – imbAF
    May 2 at 8:06
  • $\begingroup$ When solving the second equation, $T_1$ is already known (at least asymptotically). $\endgroup$ May 2 at 20:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.