Prove that $T(n) = T(n/3) + T(2n/3) + 5n$ is $O(n log n)$

Question

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?

Answer 1

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.

Answer 2

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))$

Answer 3

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)$$