# Closed form for recurrence relation $T(n) = T(\dfrac{n}{3}) + T(\dfrac{2n}{3}) + \mathcal{O}(n)$

I am familiar with the Master's theorem and with the idea of telescoping a recurrence relation to find a closed form, but I could not solve this one:

$$T(n) = T(\dfrac{n}{3}) + T(\dfrac{2n}{3}) + \mathcal{O}(n), \hspace{4mm} n\in \mathbb{N}$$

$T(n)$ is only defined for positive integer inputs. The context where it arises from is trying to find the dependency of a Divide and Conquer recursive algorithm splitting the input in uneven parts of $\dfrac{n}{3}$ and $\dfrac{2n}{3}$ length.

The presence of two different terms confuses me, since the strategy I usually follow is to unroll until $T(1)$ appears, where it is a known value that can be substituted ($0$ in the case of sorting algorithms, for example).

• It seems like the method en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method implies that $T(n) = \mathcal{O}(n \log(n))$ but this is not my area Commented Feb 21, 2017 at 5:22
• Thanks, but I am more interested on how to tackle it than in the solution Commented Feb 21, 2017 at 5:31
• Yes. I am pretty sure the method I linked to applies to your problem. Commented Feb 21, 2017 at 5:34
• Maybe of interest math.stackexchange.com/questions/1040199/… Commented Feb 21, 2017 at 18:35
• @user399601, yes I overlooked at your answer, the method shows the procedure not only points out the solution, thanks Commented Feb 21, 2017 at 20:35

We have $k = 2$ and $a_1 = a_2 = 0$ and $h_1 = h_2 \equiv 0$ (functions are identically zero). $b_1 = \tfrac{1}{3}$ and $b_2 = \tfrac{2}{3}$ and so $p = 1$. Thus we have $$T(x) \in \mathcal{O}\left(x\left(1 + \int_1^x \frac{g(u)}{u^{2}} du\right)\right).$$ Let us look at the integral (I don't know whether this is how this is normally written up, this is my first time as well!): $$\int_1^x \frac{g(u)}{u^2}du \in \mathcal{O}\left(\int_1^x \frac{u}{u^2} du\right) = \mathcal{O}(\log x ).$$ There is some justification to be done here that this works, having done so, we can substitute back to find $$T(x) \in \mathcal{O}(x\log x).$$ Note that the asymmetric splitting makes no difference, nor the number of partitions.