# Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the $\displaystyle T\left(n\over6\right)$ to $\displaystyle T\left(3n\over4\right)$ and then we would have $\displaystyle T(n) = 2T\left(3n\over4\right) + 5n$ for the MT to apply.

I would thereby bound the function by another function. Probably not a good solution and possibly wrong. Is there a better way to solve this?

• The Akra-Bazzi Method: en.wikipedia.org/wiki/Akra–Bazzi_method Mar 14, 2016 at 1:20
• @CarlHeckman can you help me apply this method for my example? Mar 14, 2016 at 1:30
• The Wikipedia page has a good overview of the method. You should write down the relevant constants, check that the conditions of the theorem are satisfied, and then solve or evaluate the required equations and expressions. You might need to approximate some values.
– emi
Mar 14, 2016 at 1:34
• Done while you asked. And yes, some approximation was necessary, but the approximation doesn't affect the final answer, surprisingly. Mar 14, 2016 at 1:37
• It shouldn't be that surprising: the scale factors in front of the recursive terms ($a_i$ in the Wiki Akra-Bazzi notation) are not larger than $1$, so between that and the linear term, you get something analogous to a geometric series, which is dominated by its largest term.
– Ian
Mar 14, 2016 at 2:09

Your recursion is in the right form. First, you need to solve $$\left(3\over4\right)^p + \left(1\over6\right)^p=1.$$ The important thing here is that $p\approx 0.85$, which is not an integer. Then the asymptotic behavior will be $\Theta(f(n))$, where \eqalign{f(x)&=x^p \cdot \left(1 + \int_1^x {5u \over u\,^{p+1}}\,du \right) =x^p \cdot \left(1 + 5\cdot\int_1^x u^{-p}\,du \right) \cr&= x^p \cdot \left(1 + {5 x^{1-p} - 5\over {1-p}}\right) = c_1 x^p + c_2 x, \cr} for appropriate constants $c_1$ and $c_2$. This means the growth rate is $\Theta(x)$.
• How do you solve $$\left(3\over4\right)^p + \left(1\over6\right)^p=1.$$? Aug 14, 2019 at 17:14