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$. Also, specify an asymptotic bound.

Clearly $T(n)\in \Omega(n)$ because of the constant factor.  The recursive nature hints at a possibly logarithmic runtime (because $T(n) = T(n/2) + 1$ is logarithmic, something similar may occur for the problem here).  However, I'm not sure how to proceed from here.
Even though the recurrence does not specify an initial value (i.e. $T(0)$), if I set $T(0) = 1$ some resulting values are:
  0     1
100   831
200  1939
300  3060
400  4291
500  5577
600  6926
700  8257
800  9665
900 10933

The question:  Is there a technique that I can use to solve the recurrence in terms of $n$ and $T(0)$?  If that proves infeasible, is there a way to determine the asymptotic behavior of the recurrence?
 A: This calls for the use of the  Akra-Bazzi Method. Given that $T(n) = T(n/4) + T(3n/4) +n$, we have that
\begin{align}
g(n)= n,\\ 
a_1  = 1, a_2 = 1 ~\mbox{and}\\
b_1= 1/4, b_2 = 3/4
\end{align}
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
\begin{align}
f(x)
= x^p (1+ \int _{[1,x]} \frac{g(u)}{u^{1+p}} du)  \\
= x(1+ \log(x))
\end{align}
Thus $T(n) = \Theta(n \log(n))$.
A: $T(n)=T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)+n$
$T(n)-T\left(\dfrac{n}{4}\right)-T\left(\dfrac{3n}{4}\right)=n$
For the particular solution part, getting the close-form solution is not a great problem.
Let $T_p(n)=An\ln n$ ,
Then $An\ln n-\dfrac{An}{4}\ln\dfrac{n}{4}-\dfrac{3An}{4}\ln\dfrac{3n}{4}\equiv n$
$An\ln n-\dfrac{An}{4}(\ln n-\ln4)-\dfrac{3An}{4}(\ln n+\ln3-\ln4)\equiv n$
$\dfrac{(4\ln4-3\ln3)An}{4}\equiv n$
$\therefore\dfrac{(4\ln4-3\ln3)A}{4}=1$
$A=\dfrac{4}{4\ln4-3\ln3}$
$\therefore T_p(n)=\dfrac{4n\ln n}{4\ln4-3\ln3}$
But getting the complementary solution part is not optimistic.
Since we should handle the equation $T_c(n)-T_c\left(\dfrac{n}{4}\right)-T_c\left(\dfrac{3n}{4}\right)=0$ .
