How to prove asymptotic solution for recurrence equation: $T(n) = 2T(n/4)+4T(n/8) + n$ for $n>8$ with $T(n) = 1$ for $1 \leq n \leq 8$?

Question

As title says, how does one solve $T(n) = 2T(n/4)+4T(n/8)+n$ for $n>8$ with $T(n)=1$ when $1 \leq n \leq 8$?

Answer 1

Suppose we start by solving the following recurrence: $$T(n) = 2T(\lfloor n/4 \rfloor) + 4T(\lfloor n/8 \rfloor) + n$$ where $T(1) = 1$ and $T(0) = 0.$

We will adapt this solution to the case where $T(n) = 1$ when $1\le n\le 8.$

Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$

We unroll the recursion to obtain an exact formula for $n\ge 1$ $$T(n) = [z^{\lfloor \log_2 n \rfloor}] \frac{1}{1-2z^2-4z^3} + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-2z^2-4z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

Now the roots of $1-2z^2-4z^3$ are $$\rho_0 = \frac{1}{2}, \quad\rho_{1,2} = -\frac{1}{2} \pm \frac{1}{2}i$$

Applying partial fractions by residues we obtain $$\mathrm{Res}_{z=\rho_0} \frac{1}{1-2z^2-4z^3} = \frac{1}{-4\rho_0-12\rho_0^2} = -\frac{1}{5}$$

and $$\mathrm{Res}_{z=\rho_{1,2}} \frac{1}{1-2z^2-4z^3} = \frac{1}{5} \left(\frac{1}{2}\mp i\right)$$

Using $$[z^j] \frac{1}{z-\rho} = - [z^j] \frac{1}{\rho} \frac{1}{1-z/\rho} = -\frac{1}{\rho^{j+1}}$$ this yields

$$[z^j] \frac{1}{1-2z^2-4z^3} = \frac{1}{5} 2^{j+1} - \frac{1}{5} \left(\frac{1}{2} - i\right) \rho_1^{-j-1} - \frac{1}{5} \left(\frac{1}{2} + i\right) \rho_2^{-j-1}$$

which becomes $$\frac{1}{5} 2^{j+1} -\frac{1}{5} \left(-\frac{3}{2}+\frac{1}{2}i\right) \sqrt{2}^j \exp(-3/4\pi i j) -\frac{1}{5} \left(-\frac{3}{2}-\frac{1}{2}i\right) \sqrt{2}^j \exp(+3/4\pi i j)$$

which finally yields $$\frac{1}{5} 2^{j+1} + \frac{3}{5} \sqrt{2}^j \cos(3/4 \pi j) - \frac{1}{5} \sqrt{2}^j \sin(3/4 \pi j).$$

This admits some additional simplification as in $$\frac{1}{5} 2^{j+1} + \frac{\sqrt{10}}{5} \frac{3}{\sqrt{10}} \sqrt{2}^j \cos(3/4 \pi j) - \frac{\sqrt{10}}{5} \frac{1}{\sqrt{10}} \sqrt{2}^j \sin(3/4 \pi j).$$

Putting $\beta = \arctan(3, -1) \approx -0.3217505544$ where the first argument of the arctangent is the $y$ coordinate as implemented in Maple or the C math library we get $$c_j = \frac{1}{5} 2^{j+1} + \frac{\sqrt{10}}{5} \sqrt{2}^j \sin(3/4 \pi j + \beta).$$

We now compute lower and upper bounds which are actually attained and cannot be improved upon. For the lower bound consider a one digit followed by a string of zeroes, to give

$$T(n) \ge c_{\lfloor \log_2 n\rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} c_j 2^{\lfloor \log_2 n \rfloor-j} \\ = c_{\lfloor \log_2 n\rfloor} + 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} c_j 2^{-j} \\ = c_{\lfloor \log_2 n\rfloor} + \frac{2}{5} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} \frac{\sqrt{10}}{5} \frac{1}{\sqrt{2}^j} \sin(3/4 \pi j + \beta).$$

The sum term can be shown to converge to a number (albeit very slowly) namely $8/25$ and we get the lower bound asymptotic

$$c_{\lfloor \log_2 n\rfloor} + \frac{2}{5} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + \frac{8}{25}2^{\lfloor \log_2 n \rfloor}.$$

We see that the middle term dominates.

For an upper bound consider a string of one digits to get $$T(n) \le c_{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} c_j \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\ = c_{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} c_j (2^{\lfloor \log_2 n \rfloor -j +1} -1).$$

The same constant appears as in the lower bound, multiplied by a factor of two.

We get as a first asymptotic $$c_{\lfloor \log_2 n\rfloor} + \frac{4}{5} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + \frac{16}{25}2^{\lfloor \log_2 n \rfloor}.$$

The error term being subtracted is $$\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} c_j$$ with dominant asymptotics $$\frac{2}{5} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 2^j \sim \frac{2}{5} 2^{\lfloor \log_2 n \rfloor}$$

for a final upper bound asymptotic $$c_{\lfloor \log_2 n\rfloor} + \frac{4}{5} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + \frac{6}{25}2^{\lfloor \log_2 n \rfloor}.$$

Joining the upper and the lower bound we get for the asymptotics of the recurrence that it is

$$T(n)\in\Theta\left(\lfloor \log_2 n \rfloor \times 2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(\lfloor \log_2 n \rfloor 2^{\ \log_2 n}\right) = \Theta(n \times \log n),$$ which, let it be said, could also have been obtained by inspection.

Remark. We can merge the first term from the exact formula into the sum but this does not affect the proceedings and is left at the reader's discretion. This is

$$\sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-2z^2-4z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$

To complete this computation we now take into account that the OP asked for a solution where $T(n) = 1$ for $1\le n\le 8.$ Call this $S_2(n).$

First solve for $S_1(n)$ where $S_1(n) = 1$ for $1\le n\le 15.$

We obtain the exact formula for $n\ge 16$ $$\sum_{j=0}^{\lfloor \log_2 n \rfloor -4} [z^j] \frac{1}{1-2z^2-4z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} + \sum_{j=\lfloor \log_2 n \rfloor -3}^{\lfloor \log_2 n \rfloor -2} [z^j] \frac{1}{1-2z^2-4z^3} \\ + [z^{\lfloor \log_2 n \rfloor -1}] \frac{4z^3}{1-2z^2-4z^3}.$$

Finally we need to correct for the interval $8\lt n\le 15$ where $S_1$ assigns the value one instead of $T(n).$ Introduce $$ q = \lfloor n/2^{\lfloor \log_2 n \rfloor-3} \rfloor.$$

This completes the formula, adding the correction factor (Iverson bracket) $$[[q\gt 8]] \times (q+5) \times [z^{\lfloor \log_2 n \rfloor -3}] \frac{1}{1-2z^2-4z^3}.$$

It then follows by inspection that the asymptotics of $S_2(n)$ are the same as those of $T(n).$

Addendum. The evaluation of the constant follows from $$\left. \frac{1}{1-2z^2-4z^3} + \frac{1}{5}\frac{1}{z-1/2}\right|_{z=1/2} = \left. 1/5\,{\frac {2\,z+3}{2\,{z}^{2}+2\,z+1}} \right|_{z=1/2} = \frac{8}{25}.$$