How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?
We guess that $T(n) = \Theta(n^{\alpha})$, where $\alpha &gt; 0$ is a constant.

To find $c$, we use the substitution method.

Assume that $T(n) \le cn^{\alpha}$. (The other direction $T(n) \ge cn^{\alpha}$ is similar.) 

Then, we have $$T(n) \le c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha}.$$

Letting $$c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha} = cn^{\alpha},$$ we obtain that $$(1/2)^{\alpha} + (1/4)^{\alpha} + (1/8)^{\alpha} = 1.$$

Solving this equation (using Mathematica) yields 
$$\alpha = 0.879146.$$