Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
\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))$.

share|cite|improve this answer
That's really nice. I hadn't heard of that result. Thanks. – marty cohen Oct 18 '12 at 1:42



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

share|cite|improve this answer
Why resurrect this (answered) question from 2+ years ago? – Did Jan 18 '15 at 11:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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