# Resolving this recurrence equation [duplicate]

I have this recurrence equation:

$T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$

$T(1) = 1$

I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.

• What have you tried so far? What have you looked up? What are you confused about? – jason328 Apr 14 '13 at 19:20
• Hi jason, i would like to know which are the steps to follow to solve that recurrence equation (and recurrence equation in general). Thanks for help, Federico – Federico Ponzi Apr 15 '13 at 11:02
• The easiest way is to use Master theorem. – Bartosz Przybylski Apr 29 '13 at 12:24
• If you want to see how to come up with recursion equations, you can see the base question, and read through the answers, to get result for general approach. – user742 Apr 29 '13 at 12:25
• Try the reference question: cs.stackexchange.com/questions/2789/… – Aryabhata Apr 29 '13 at 16:48

Construct a recursion tree. The sum of the costs per level is less then $c\cdot n$, for $c$ being the constant in the $O(n)$. The tree has roughly $n\log_4 n$ full levels, and the deepest level is $n \log_{4/3} n$. So, summing up over all levels gives $T(n)=O(n\log n)$.