# Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$

I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:

$$T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$$

So I tried to find the general Big-oh complexity, so that I could solve each one just by substituting in the particular coefficient values. Here is what I did:

\begin{aligned} T(n)&=a\left(aT\left(\frac{n}{\alpha^{2}}\right)+bT\left(\frac{\beta n}{\alpha^{2}}\right)+f\left(\frac{n}{\alpha}\right)\right)+b\left(aT\left(\frac{\beta n}{\alpha^{2}}\right)+bT\left(\frac{\beta^{2} n}{\alpha^{2}}\right)+f\left(\frac{\beta n}{\alpha}\right)\right)+f(n)\\ &=\left(a^{2}T\left(\frac{n}{\alpha^{2}}\right)+2abT\left(\frac{\beta n}{\alpha^{2}}\right)+b^{2}T\left(\frac{\beta^{2}n}{\alpha^{2}}\right)\right)+\left(f(n)+af\left(\frac{n}{\alpha}\right)+bf\left(\frac{\beta n}{\alpha}\right)\right)\\ &=\sum_{r=0}^{k}{k\choose r}a^{k-r}b^{r}T\left(\frac{\beta^{r}n}{\alpha^{k}}\right)+\sum_{r=0}^{k-1}\sum_{i=0}^{r}{r\choose i}a^{r-i}b^{i}f\left(\frac{\beta^{i}n}{\alpha^{r}}\right) \end{aligned} $$\boxed{O\left[\max\left(\sum_{r=0}^{k}{k\choose r}a^{k-r}b^{r}T\left(\frac{\beta^{r}n}{\alpha^{k}}\right), \sum_{r=0}^{k-1}\sum_{i=0}^{r}{r\choose i}a^{r-i}b^{i}f\left(\frac{\beta^{i}n}{\alpha^{r}}\right)\right)\right]\text{ where } k=\log_{\alpha}n}$$

Is this correct? When I apply it on a specific example, I'm not sure if I get the right answer. Any help is appreciated. Thanks in anticipation.

You can solve this (for well-behaved $$f$$) using the Akra–Bazzi theorem, a generalization of the master theorem. The answer will depend on the relation between the parameters $$a,b,\alpha,\beta$$ and the asymptotics of $$f$$.