# Asymptotic bounds of $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.

I have the answer to it, but I don't understand it.

The answer is, $T(n) = \Theta(n)$.

It would be really good if you can explain it using recursion tree.

You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.

Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n.$$

Then we have the following exact formula for $T(n)$: $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Now let $\rho_{1,2,3}$ be the inverses of the roots of $$1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3$$ where $$\rho_1 \approx 0.9196433771 \quad \text{and} \quad \rho_{2,3} \approx -0.2098216888 \pm 0.3031453647 i$$ so that $\rho_1$ dominates.

Solving for $c_{1,2,3}$ in $$[z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} = c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j$$ we obtain $$c_1 \approx 0.6184199255 \quad \text{and} \quad c_{2,3} \approx 0.1907900392 \mp 0.01870058304 i.$$

To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} 2^{\lfloor \log_2 n \rfloor} \\ = 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} (c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j) = 2^{\lfloor \log_2 n \rfloor} \left( c_1 \frac{1-\rho_1^{\lfloor \log_2 n \rfloor +1}}{1-\rho_1} + c_2 \frac{1-\rho_2^{\lfloor \log_2 n \rfloor +1}}{1-\rho_2} + c_3 \frac{1-\rho_3^{\lfloor \log_2 n \rfloor +1}}{1-\rho_3} \right).$$ This bound is actually attained.

For an upper bound, consider the case of a string of ones, $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1 - \frac{1}{2} z - \frac{1}{4} z^2 - \frac{1}{8} z^3} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \\ = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (c_1 \rho_1^j + c_2 \rho_2^j + c_3 \rho_3^j) (2^{\lfloor \log_2 n \rfloor +1} - 2^j) \\ = 2^{\lfloor \log_2 n \rfloor +1} \left( c_1 \frac{1-\rho_1^{\lfloor \log_2 n \rfloor +1}}{1-\rho_1} + c_2 \frac{1-\rho_2^{\lfloor \log_2 n \rfloor +1}}{1-\rho_2} + c_3 \frac{1-\rho_3^{\lfloor \log_2 n \rfloor +1}}{1-\rho_3} \right) \\ - \left( c_1 \frac{(2\rho_1)^{\lfloor \log_2 n \rfloor +1}-1}{2\rho_1-1} + c_2 \frac{1-(2\rho_2)^{\lfloor \log_2 n \rfloor +1}}{1-2\rho_2} + c_3 \frac{1-(2\rho_3)^{\lfloor \log_2 n \rfloor +1}}{1-2\rho_3} \right).$$ This bound too is actually attained.

To conclude we compute the asymptotics. We see that $|\rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to $$2^{\lfloor \log_2 n \rfloor} \left(\frac{c_1}{1-\rho_1} +\frac{c_2}{1-\rho_2} +\frac{c_3}{1-\rho_3} \right) = 8 \times 2^{\lfloor \log_2 n \rfloor}.$$

We also have $|2| > |2\rho_1|$ and hence the upper bound is asymptotic to $$2\times 2^{\lfloor \log_2 n \rfloor} \left(\frac{c_1}{1-\rho_1} +\frac{c_2}{1-\rho_2} +\frac{c_3}{1-\rho_3} \right) = 16 \times 2^{\lfloor \log_2 n \rfloor}.$$ It follows that $$T(n) \in \Theta \left(2^{\lfloor \log_2 n \rfloor} \right) = \Theta\left(n\right)$$ with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $\lfloor \log_2 n \rfloor$ is off by almost one from the correct value $\log_2 n,$ which turns the sixteen back into eight.

Here are the top two layers of the recursion tree: All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,\text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be $$n+\left(\frac{7}{8}\right)n+\left(\frac{7}{8}\right)^2n+\left(\frac{7}{8}\right)^3n+\cdots$$ so we have a geometric series and thus $$T(n)\le \frac{1}{1-\frac{7}{8}} = 8n$$ for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)\ge 2n$. Putting these together gives us the desired bound, $T(n)=\Theta(n)$.

• Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c \in \mathbb{Z}_{\gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{\log_2{n}}$, which is superlinear. – void-pointer Mar 22 '16 at 6:03
• what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ? – vikkyhacks Jan 9 '17 at 14:15

Using Akra–Bazzi method

$$a_1=a_2=a_3=1$$

$$b_1=2, b_2=4,b_3=8$$

$$f(n)=n$$

$$a_i > 0, b_i > 0$$

$$\cfrac{a_1}{b_1^p}+\cfrac{a_2}{b_2^p}+\cfrac{a_3}{b_3^p}=1$$

$$\left(\cfrac{1}{2}\right)^p+\left(\cfrac{1}{4}\right)^p+\left(\cfrac{1}{8}\right)^p=1$$

$$T(n)=Θ\left(n^p\left(1+\int_n^1 \frac{f(x)}{x^{p+1}} \, dx \right)\right)$$

$$\int_n^1 \frac{x}{x^{p+1}} \, dx=n^{1-p}$$

$$\implies T(n)=Θ\left(n^p\left(1+ n^{1-p}\right)\right) = \left(n^p\right)*\left(n^{1-p}\right) = Θ\left(n\right)$$ Hence,

$$T(n) = Θ\left(n\right)$$

                              a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n

ai>0 , bi>0

(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1

T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))

∫n1x/x^p+1dx=n^1-p

T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)

T(n)=Θ(n)

• here is a mathjax guide to type maths on this site. – Siong Thye Goh Jan 27 '19 at 12:31
• For anyone studying Algorithms from Intro to Algorithms by CLRS you can find this Akra-Bazzi method to solve such recurrences at the end of Divide and Conquer Chapter – Syed Souban Aug 14 '19 at 16:49