Calculate the complexity of $T\left( n\right) =T\left( \dfrac{n}{3}\right) +T\left( \dfrac{2n}{3}\right) +\theta \left( 1 \right)$
Without using the master theorem.
My take on this:
I found that the answer should be $\theta \left( n \right)$ but I have issues proving the upper bound (big O), even when using induction (the lower bound is quite easy to show using induction).
As I understand it, the total amount of work is the amount of nodes in the recursion tree, since the work on each node is $\theta \left( 1 \right)$.
But how many nodes are there? I tried using the fact that the height of the tree is $\log _{1.5}{n}$ and to bound it from above with the amount of nodes in a complete, perfectly balanced binary tree of height $\log _{1.5}{n}$, which is $2^{\log _{1.5}\left( n\right) +1}-1$, but I can't get $O\left( n\right)$ no matter what do I do, and I can’t think of a better bound.
Edit: I also saw this: How to solve the recurrence $T(n) = T(n/3) + T(2n/3)$? but didn't quite understand the answer, might not be something that we have covered
By using the substitution method one can show that the complexity of the recurrence relation you stated is $O(n)$. Let $T(n) = T(n/3) + T(2n/3) + c$ and assume $T(n) \leq kn - d$ for some constants $k$ and $d$, then by induction:
$$T(n) = k\frac{n}{3} - d + k\frac{2n}{3} - d + c$$
$$T(n) = kn - 2d + c \leq kn - d$$
The last inequality holds, if e.g. $d \geq c$. And so we conclude $T(n) = O(n)$. You did not provide a base case, so this case was not considered.