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

Question

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?

Answer 1

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

Answer 2

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