1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented May 2, 2022 at 0:22
  • $\begingroup$ @plshelp You should post that as an answer. $\endgroup$
    – Nathaniel
    Commented May 2, 2022 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
    Commented May 2, 2022 at 8:06
  • $\begingroup$ When solving the second equation, $T_1$ is already known (at least asymptotically). $\endgroup$
    – user16034
    Commented May 2, 2022 at 20:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.