World's most popular travel blog for travel bloggers.

[Solved]: Resolving this recurrence equation

, , No Comments
Problem Detail: 

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.

Asked By : Federico Ponzi

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback