Recursive trees

Question

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a constant for $n \leq 4$ and $n = 4k$ for some integer $k$). $T(n) = T(n/4) + T(3n/4) + O(n) $. The answer is $n\log n$ but i can't figure out why?

Answer 1

If you plot the tree, you start with $$T(n)\rightarrow O(n)$$ Then making from it $$T \left(\frac n4 \right)+T\left(\frac34n \right) \rightarrow O(n)$$ And again: $$T \left(\frac n{16} \right)+\left(\frac {3}{16}n \right)+T\left(\frac3{16}n \right)+T\left(\frac9{16}n \right) \rightarrow O(n)$$

Well, the idea is that any row produces $O(n)$. Since every row divides $n$ by a factor, the height of the tree is $\log n$ (actually, larger than $\log_4 n$ but $\log_{4/3}n$), and multiplying it makes $n \log n.$