0
$\begingroup$

$\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?

$\endgroup$
6
  • $\begingroup$ The Akra-Bazzi Method: en.wikipedia.org/wiki/Akra–Bazzi_method $\endgroup$
    – Christopher Carl Heckman
    Mar 14, 2016 at 1:20
  • $\begingroup$ @CarlHeckman can you help me apply this method for my example? $\endgroup$
    – user3393266
    Mar 14, 2016 at 1:30
  • $\begingroup$ 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. $\endgroup$
    – emi
    Mar 14, 2016 at 1:34
  • $\begingroup$ Done while you asked. And yes, some approximation was necessary, but the approximation doesn't affect the final answer, surprisingly. $\endgroup$
    – Christopher Carl Heckman
    Mar 14, 2016 at 1:37
  • $\begingroup$ 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. $\endgroup$
    – Ian
    Mar 14, 2016 at 2:09

1 Answer 1

Reset to default
3
$\begingroup$

Since that link didn't work -- you can go to https://en.wikipedia.org/wiki/Master_theorem and then click on the "See also" link -- here's the problem worked out.

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)$.

$\endgroup$
1
  • $\begingroup$ How do you solve $$\left(3\over4\right)^p + \left(1\over6\right)^p=1.$$? $\endgroup$
    – logdev
    Aug 14, 2019 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .