3
$\begingroup$

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?

  • 1
    Hint: try $T(n) = c n \log n$ for appropriate constant $c$.2012-10-18
  • 0
    @Robert Israel: Your trying can find the particular solution part of the recurrence relation.2013-08-12

2 Answers 2