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?
 A: 
You seem way too attached to the constant 5 and the base $3/2$. You don't need this exact constant to prove what you want, so why make your life miserable by clinging to it instead of picking "anything that works"?

Short advice: do not commit in advance to anything that makes your life harder if you can avoid it.
As an example, in your case let your induction hypothesis be 
$$
T(k) \leq C k \ln k, \qquad \forall k < n \tag{$\dagger$}
$$
($\ln$ is the natural logarithm) for some absolute constant $C>0$ that we will pick momentarily.
Then you get
$$\begin{align}
T(n) &= T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+5n \\
&\leq_{(\dagger)}  C \frac{n}{3}\ln \frac{n}{3} + C\frac{2n}{3}\ln \frac{2n}{3} + 5n\\
&\leq Cn \ln n- C\frac{n}{3}\ln 3 -  C\frac{2n}{3}\ln \frac{3}{2} + 5n \\
&\leq Cn \ln n
\end{align}$$
where the last inequality holds as long as we can choose $C$ such that
$$
C\frac{n}{3}\ln 3 +  C\frac{2n}{3}\ln \frac{3}{2} \geq 5n
$$
for all $n\geq 1$. This is satisfied for any $C$ such that
$$
C \geq \frac{5}{\frac{1}{3}\ln 3+\frac{2}{3}\ln \frac{3}{2}} \simeq 7.8
$$
so we can "retroactively" choose, say, $C\stackrel{\rm def}{=} 8$: the proof now goes through.
A: 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))$
A: One approach that can tackle recurrences like this is the Akra-Bazzi method:
$T(n) = T(n/3) + T(2n/3) + 5n$ means we must solve for $\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$, which is true for $p=1$. Then we have:
$$T(n) \in \Theta\left(n^p\left(1 + \int_{1}^{n} \frac{5u}{u^{p+1}} \, du\right)\right)$$
$$T(n) \in \Theta\left(n\left(1 + 5\int_{1}^{n} \frac{1}{u} \, du\right)\right)$$
$$T(n) \in \Theta\left(n\left(1 + 5\log(n)\right)\right)$$
$$T(n) \in \Theta\left(n + 5n\log(n)\right)$$
$$T(n) \in \Theta\left(n\log(n)\right)$$
