Supongamos que empezamos resolviendo la siguiente recurrencia: $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 4n$$ donde $T(1) = c$ y $T(0) = 0.$
Ahora dejemos que $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ sea la representación binaria de $n.$ Desenrollamos la recursión para obtener un exacto fórmula para $n\ge 2$ $$T(n) = c [z^{\lfloor \log_2 n \rfloor}] \frac{1}{1-z-z^2} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
Reconocemos la función generadora de los números de Fibonacci, por lo que la fórmula se convierte en $$T(n) = c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
Ahora calculamos los límites inferiores y superiores que se alcanzan realmente y no pueden ser mejorados. Para el límite inferior consideremos una cifra seguido de una cadena de ceros, para dar
$$T(n) \ge c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} + 8 \times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1}.$$
Ahora bien, como $$|\varphi|=\left|\frac{1+\sqrt{5}}{2}\right|<2$$ el término de la suma converge a un número, tenemos $$\frac{1}{2} \le \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1} \lt \sum_{j=0}^{\infty} F_{j+1} 2^{-j-1} = 2.$$
Para un límite superior considere una cadena de un dígito para obtener
$$T(n) \le c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j} - 1) \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor+1-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 4 \times 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j} \\ = c F_{\lfloor \log_2 n \rfloor +1} - 4 (F_{\lfloor \log_2 n \rfloor +2} -1) + 16 \times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1}.$$
Aparece la misma constante que en el límite inferior. Ahora bien, como el término $F_{\lfloor \log_2 n \rfloor}$ está asintóticamente dominado por $2^{\lfloor \log_2 n \rfloor}$ (tenemos $F_{\lfloor \log_2 n \rfloor}\in o(2^{\lfloor \log_2 n \rfloor})$ porque $F_{\lfloor \log_2 n \rfloor} \in\Theta(\varphi^{\lfloor \log_2 n \rfloor}))$ uniendo el superior y la inferior obtenemos para la asintótica de esta recurrencia que es
$$T(n)\in\Theta\left(2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\ \log_2 n}\right) = \Theta(n),$$ que, todo sea dicho, también podría haberse obtenido mediante una inspección.
Observación. La evaluación de la constante se hace observando que la función generadora de $$F_{j+1} 2^{-j-1}\quad \text{is}\quad\frac{1/2}{1-z/2-z^2/4}$$ que en $z=1$ evalúa a $\frac{1/2}{1-1/2-1/4} = 2.$ Tenemos cierta flexibilidad en cuanto a qué potencia de dos utilizar en la constante, pero esto no afecta a la asintótica.
Este Enlace MSE tiene un cálculo similar.
