2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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