<s>[INST] 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?
 [/INST] 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)$$
</s>