How can I find an asymptotic solution to this recurrence?

Question

How can I find an asymptotic solution to the recurrence

$$T(n) = 4T(n/4) + 2T(n/2) + C$$ I replaced the $4T(n/4)$ with $4T(n/2)$ and used the master theorem to get an upper bound of $O(n^{\log_2 6})$ and I replaced the $2T(n/2)$ with $2T(n/4)$ to get a lower bound of $\Omega(n^{\log_4 6})$, but how can I find a tight bound?

Answer 1

You can use a sharper form of the master theorem called the Akra-Bazzi Method.

You can find details on the linked wikipedia page, but broadly we see that

$$ T(n) = a_1 T(b_1 n) + a_2 T(b_2 n ) + g(n) = 4 T \left (\frac{1}{4} n \right ) + 2 T \left ( \frac{1}{2} n \right ) + C $$

and it's not hard to show the (extremely mild) technical conditions are met.

Then the method tells us that

$$T(n) = \Theta \left ( n^p \left ( 1 + \int_1^n \frac{g(u)}{u^{p+1}}\ du \right ) \right )$$

where $p$ is the real number so that $a_1 b_1^p + a_2 b_2^p = 1$.

For us it's not hard to show that $p = \log_2 \left ( 1 + \sqrt{5} \right )$, since the equation becomes $(2^{1-p})^2 + 2^{1-p} = 1$. Then we compute the integral

$$ \int_1^n \frac{C}{u^{p+1}}\ du = \frac{C}{p} \left (1 - n^{-p} \right ) $$

so that we finally see

$$ T(n) = \Theta \left ( n^p \left (1 + \frac{C}{p} (1 - n^{-p}) \right ) \right ) = \Theta \left ( n^p \right ) $$

for $p = \log_2 \left (1 + \sqrt{5} \right )$.

That is,

$$T(n) = \Theta \left ( n^{\log_2 \left ( 1 + \sqrt{5} \right )} \right ) \approx \Theta \left ( n^{1.694...} \right )$$

which you'll note does indeed lie within your bounds!

---

I hope this helps ^_^

Answer 2

Hint

If you let $T(n)=U(n)-\frac c5$, you end with $$U(n)=4 U\left(\frac{n}{4}\right)+2 U\left(\frac{n}{2}\right)$$ $$U(n)=c_1 \,\left(1-\sqrt{5}\right)^{\log_2 (n)}+c_2\, \left(1+\sqrt{5}\right)^{\log_2 (n)}$$