# Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Specify the best asymptotic running time.

-
Hint: try $T(n) = c n \log n$ for appropriate constant $c$. –  Robert Israel Oct 18 '12 at 0:49
@Robert Israel: Your trying can find the particular solution part of the recurrence relation. –  doraemonpaul Aug 12 '13 at 5:03

This calls for the use of the Akra-Bazzi Method. Given that $T(n) = T(n/4) + T(3n/4) +n$, we have that $g(n)= n, a_1 = a_2 = 1,b_1= 1/4, b_2 = 3/4$.
We first need to solve for $p$ subject to $(1/4)^p + (3/4)^p = 1$ , giving $p= 1$.The method now gives $T(x) \in \Theta(f(x))$, where
Thus $T(n) = \Theta(n \log(n))$.