> 
> 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?