Prove that $T(n) = T(n/3) + T2n/3) + 5n$ is $O(n log n)$ I'm doing some research about time complexity of algorithms and stumbled upon the following problem that I'm not able to solve:
Let $T(n) = T(n/3) + T(2n/3) + 5n$. prove that $T(n) = O(n log n)$
First, I made a recursion tree, which is the same as the one in the question: Recursion tree T(n) = T(n/3) + T(2n/3) + cn
I found out that each level costs $5n$ and that the leaves have different depths (The left path is the shortest with height $log_3 n$ and the one on the right is the longest with height $log_{\frac{3}{2}}n$).
Now, since we need an upper bound, I took the longest path of height $log_{\frac{3}{2}}n$. This gives total costs $5n \cdot log_{\frac{3}{2}}n$.
Now I want to prove with induction on $n$ that this is true. I proceeded in the following way:
Assume as induction hypothesis that $T(k) \leqslant 5k \cdot log_{\frac{3}{2}}k$ for $k < n$. Then:
$T(n) \leqslant T(n/3) + T(2n/3) + 5n$
$=^{IH} \frac{5}{3}n log_{\frac{3}{2}}(\frac{n}{3}) + \frac{10}{3}n log_{\frac{3}{2}}(\frac{2n}{3}) + 5n$
$= \frac{25}{3}n log_{\frac{3}{2}} n - \frac{5}{3}n log_{\frac{3}{2}} 3 - \frac{10}{3}n log_{\frac{3}{2}} 3 + 5n$
$= \frac{25}{3}n log_{\frac{3}{2}} - 5n log_{\frac{3}{2}} 3 + 5n$
And this is certainly not smaller then or equal to $5n \cdot log_{\frac{3}{2}}n$. I've spend an entire day now on solving this recurrence relation, but nothing solved it so far. Could you help me solving this problem?

If you wish to use the recursive tree approach instead:
First level work: $5n$
Second level work: $5n/3 + 10n/3 = 5n$
Third level work: $5n/9 + 10n/9 + 10n/9 + 20n/9 = 5n$
And so on and so on.
In other words, each complete level has total work $5n$. Every leaf in the recursion tree has depth between $\log_3(n)$ and $\log_{3/2}(n)$. To derive an upper bound, we overestimate $T(n)$ by ignoring the base cases and extending the tree downward to the level of the deepest leaf, and for the lower bound, likewise to the shallowest leaf. So we have bounds $5n \log_{3}(n) \leq T(n) \leq 5n \log_{3/2}(n)$. These bounds differ by a constant factor, so $T(n) \in \Theta(n \log(n))$
