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.
 A: 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)$. 
A: 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)

