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.

  • 3
    $\begingroup$ What have you tried so far? What have you looked up? What are you confused about? $\endgroup$ – jason328 Apr 14 '13 at 19:20
  • $\begingroup$ 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 $\endgroup$ – Federico Ponzi Apr 15 '13 at 11:02
  • $\begingroup$ The easiest way is to use Master theorem. $\endgroup$ – Bartosz Przybylski Apr 29 '13 at 12:24
  • $\begingroup$ 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. $\endgroup$ – user742 Apr 29 '13 at 12:25
  • 1
    $\begingroup$ Try the reference question: cs.stackexchange.com/questions/2789/… $\endgroup$ – 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)$.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.