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

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

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.

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)