If $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $. How is the upper bound achieved?

Question

Trying to show that if $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $ using a tree, I do know that taking the shortest path gives a lower bound of the number of steps equivalent to $n\log n$. Trying to take the long path, I try to do it the same but I don't quite see how using ${3\over 2}$ as the logarithm base is legitimate or intuitively substantial. It also seems like I am not supposed to do that. I am a little lost here. Do you have a perspective on it?

Answer 1

By iterating the recursion, $$ T(n) = T\left(\frac{n}{9}\right)+2\cdot T\left(\frac{2n}{9}\right)+T\left(\frac{4n}{9}\right)+2n $$ as well as: $$ T(n) = T\left(\frac{n}{27}\right)+3\cdot T\left(\frac{2n}{27}\right)+3\cdot T\left(\frac{4n}{27}\right)+T\left(\frac{8n}{27}\right)+3n $$ so, by induction: $$ T(n) = kn+\sum_{h=0}^{k}\binom{k}{h}T\left(\frac{2^h n}{3^k}\right).$$ If we take $k=\left\lceil \log_{3/2}(n)\right\rceil$ and assume that $T(n)$ is bounded by $C$ for any $n\in [0,1]$, we get: $$ T(n) \leq n \log_{3/2}(n) + C\sum_{h=0}^{k}\binom{k}{h} \ll \frac{n\log n}{\log 3-\log 2} + Cn^{\frac{\log 2}{\log 3-\log 2}}\ll n\log n+n^{\sqrt{3}} $$ since $\sum_{h=0}^{k}\binom{k}{h}=2^k$.