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

Question

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?

Answer 1

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

Answer 2

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