I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and that f(n) is n, but I can't figure out what b is since there are two terms.
How should the recurrence be solved?
$T(n) = T(n/3) + T(2n/3) +n$
EDIT
Original Problem
A recursive algorithm has the following structure: it cuts the input of size n into three equal
pieces (of size n/3), does some work that takes a linear amount of time, and then makes two
recursive calls. The first recursive call is on a subproblem made up of one of the three pieces
and the second is on a subproblem made out of two of these pieces put together.
I think my recurrence is right based on the problem but I'm not entirely sure.
Best Answer
For this you can use Akra-Bazzi method.
But recurrence graph can help equally well.
If you have $T(n)$ as top node, then in the previous step you have had these nodes (sum of which gives $T(n)$)
$$T(\frac{n}{3})|T(\frac{2n}{3})|n$$
The next level has had these nodes ($n$ is added from the previous level):
$$T(\frac{n}{9}),T(\frac{2n}{9}),\frac{n}{3}|T(\frac{2n}{9}),T(\frac{4n}{9}),\frac{2n}{3},n$$
So you have at this level
$$T(\frac{n}{9}),(2)T(\frac{2n}{9}),T(\frac{4n}{9}),2n$$
Notice that because $\frac{n}{3}+\frac{2n}{3}=n$ each level will have a node with $n$ as a value. (2) above signifies the number of nodes.
Instead of trying to do this manually one level at a time, the structure of nodes after $N$ steps is the same as what in symbolic notation you would have after deriving
$$(x\frac{1}{3}+y\frac{2}{3})^N=\sum_{k=0}^{N}\binom{N}{k}x^{N-k}\frac1{3^{N-k}}y^{k}\frac{2^k}{3^k}$$
Now you simply replace any $x^py^q$ with $T(n^*)$ and there you have the structure after $N$ steps, of course we will add $Nn$.
$$\sum_{k=0}^{N} \binom{N}{k}T(\frac{2^k}{3^N}n)+Nn$$
The question of how many levels you have is easily answered by looking at $\frac{2^k}{3^N}n$ because this one will never go lower than 1. So N is obviously $\sim \log(n)$ because $\frac{2^k}{3^N}$ is exponential.
So in the end we can safely assume $T(n) \sim n\log(n)$. Since we do not know what $T(1)$ is and this will affect the evaluation since this value will be multiplied by the number of the leaf nodes, we take $T(n) \cong an\log(n)$ and try to calculate the asymptotic value of $a$. Even though it is not necessary, we just want to confirm the finding.
$$an\log(n)=\frac{1}{3}an\log(\frac{n}{3})+\frac{2}{3}an\log(\frac{2n}{3})+n$$ $$\frac{1}{3}a\log(\frac{1}{3})+\frac{2}{3}a\log(\frac{2n}{3})+1=0$$
or
$$a=\frac{3}{3\log(3)+2\log(2)}$$
and there you have it:
$$T(n) \cong \frac{3}{3\log(3)+2\log(2)} n\log(n)$$