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

Question

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

Answer 1

Answer to the problem is O(n*log_3/2(n)).
Use Recursive tree method instead of substitution method.

Refer this to know about recursive tree method.

Answer 2

We can use user399601's suggested Akra-Bazzi method, I will use the notation from there.

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.