# Master Theorem on $T_1(n) = 5 \cdot T_1 (\frac{n}{3}) + T_1(\frac{2n}{3}) + 3\cdot n$

There are the following recurrences:

For $$T_1(n)$$, can I just say that it is $$5 \cdot (\frac{n}{3})^k$$ + $$(\frac{2n}{3})^k$$ and then $$5 \cdot (\frac{1}{3})^1$$ + $$(\frac{2\cdot 1}{3})^1$$ = $$\frac{7}{3} > 1$$ which means that $$T_1(n)$$ = O(n)

For $$T_2(n)$$, I would do the following: $$\frac{n}{4}$$ + $$2 \cdot \frac{n}{16}$$ + $$n^{1/2}$$ $$= \frac{0.5}{4} + 2 \cdot \frac {0.5}{16} = \frac{5}{16} < 1$$, which means that $$T_2(n)$$ = $$O(n^{0,5})$$

For $$T_3(n)$$, I would say: $$(\frac{3n}{4})$$ + $$(2 \cdot \frac{n}{16})$$ and then $$(\frac{3 \cdot 1}{4})$$ + $$(2 \cdot \frac{1}{16}) = \frac{7}{8} < 1$$, which means that $$T_3(n) = O(n)$$.

Can you please tell me if what I've done is right?

These recurrences don't fit the required format for the Master Theorem. The Akra-Bazzi method might be more fitting.

For $$T_1(n)$$, we have $$g(n) = 3n$$ and we solve for $$5 \cdot (\frac{1}{3})^p + (\frac{2}{3})^p = 1$$, which holds for $$p=2$$. Then we have

$$T_1(n) \in \Theta\left(n^2\left(1 + \int_1^{n}\frac{3u}{u^{2+1}}du\right)\right) \implies \Theta(4n^2 - 3n) \implies \Theta(n^2)$$

For $$T_2(n)$$, we have $$g(n) = \sqrt{n}$$ and we solve for $$(\frac{1}{4})^p + 2 \cdot (\frac{1}{16})^p = 1$$, which holds for $$p=\frac{1}{2}$$. Then we have

$$T_2(n) \in \Theta\left(n^{1/2}\left(1 + \int_1^{n}\frac{\sqrt{u}}{u^{1/2+1}}du\right)\right) \implies \Theta\left(\sqrt{n}\left(\log{n} +1\right)\right) \implies \Theta(\sqrt{n} \log{n})$$

For $$T_3(n)$$, we have $$g(n) = 4n$$ and we solve for $$(\frac{3}{4})^p + 2 \cdot (\frac{1}{16})^p = 1$$, which holds for $$p= 0.81471381...$$ or so, but the important thing to note is that $$p < 1$$, which will be useful later. Then we have

$$T_3(n) \in \Theta\left(n^p\left(1 + \int_1^{n}\frac{4u}{u^{p+1}}du\right)\right) \implies \Theta\left(\frac{4 n^p}{p - 1} + n^p - \frac{4 n}{p - 1}\right) \implies \Theta(n)$$

I think you have almost done this right - this seems like a computer science problem, it might have better been put on a different Stack Exchange site....

Note that the Master theorem must consider when your calculated fractions don't match the polynomial degree of the "special" merge term at the end. In the $$T_3$$ function, you dealt with this properly, as $$\dfrac{7}{8} < 1$$ allows you to simply say O(n).

However you didn't look like you considered that at all for $$T_1$$. Keep in mind that the calculation you are performing tells you whether a function is "deflating" or "inflating." If the value in each $$T_i$$ is decreasing, but the total value across the recursive calls is { \it increasing }, then your function must be exponential on it's input, which you should have gotten for $$T_1$$ (and the master theorem tells you how to deal with that, although I think you can solve them without it too).