Cómo analizar la complejidad temporal $\Theta$ de esta recurrencia

Question

Estoy tratando de entender cómo demostrar que

$$T(n) = T(n/2) + T(n/4) + n^2$$

es $\Theta(n^2)$ mediante un árbol de recursión. Al principio probé con la sustitución, pero se complicó enseguida.

Esto es autoestudio. El problema es de este pdf problema 1-12.

Answer 1

Supongamos que empezamos resolviendo la siguiente recurrencia: $$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + n^2$$ donde $T(1) = 1$ 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 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-z-z^2} \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)^2.$$

Reconocemos la función generadora de los números de Fibonacci, por lo que el fórmula se convierte en $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)^2.$$

Ahora calculamos los límites inferior y superior que se alcanzan realmente y no pueden mejorarse. Para el límite inferior, consideremos un dígito seguido de una cadena de ceros, para obtener

$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 4^{\lfloor \log_2 n \rfloor-j} = 4^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 4^{-j}.$$

Ahora que $$\left|\frac{1+\sqrt{5}}{2}\right|<4$$ el término de la suma converge a un número, tenemos $$1 \le \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 4^{-j} \lt \sum_{j=0}^{\infty} F_{j+1} 4^{-j} = \frac{16}{11}$$

y así obtenemos para la asintótica $$\frac{16}{11} 4^{\lfloor \log_2 n \rfloor}.$$

Para un límite superior considere una cadena de un dígito para obtener

$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}\right)^2 = \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j} - 1)^2 \\ = 4\times 4^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 4^{-j} - 4\times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 2^{-j} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} \\ = 4\times 4^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 4^{-j} - 4\times 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1} 2^{-j} + F_{\lfloor \log_2 n \rfloor + 3} - 1.$$

Aparece la misma constante que en el límite inferior, así como una constante adicional. Calculándolas obtenemos $$\frac{64}{11} \times 4^{\lfloor \log_2 n \rfloor} - 16\times 2^{\lfloor \log_2 n \rfloor} + F_{\lfloor \log_2 n \rfloor + 3} - 1.$$

Haciendo la asintótica de estos tres términos obtenemos un término en $n^2$ , un término en $n$ y un término en $n^{\log_2 \varphi} \in o(n)$ donde $\varphi$ es la proporción áurea.

Uniendo el límite superior y el inferior obtenemos para la asíntota de esta recurrencia que es

$$T(n)\in\Theta\left(4^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{2\log_2 n}\right) = \Theta(n^2),$$ que, todo sea dicho, también podría haberse obtenido mediante inspección.

Observación. La evaluación de la constante se realiza observando que la función generadora de $$F_{j+1} 4^{-j}\quad \text{is}\quad\frac{1}{1-z/4-z^2/16}$$ que en $z=1$ se evalúa como $\frac{1}{1-1/4-1/16} = \frac{16}{11}.$

Del mismo modo tenemos la función generadora de $$F_{j+1} 2^{-j}\quad \text{is}\quad\frac{1}{1-z/2-z^2/4}$$ que en $z=1$ se evalúa como $\frac{1}{1-1/2-1/4} = 4.$

Tenemos cierta flexibilidad en cuanto a la potencia de cuatro a utilizar en el constante, pero esto no afecta a la asintótica.

Una recurrencia estrechamente relacionada que es algo más simple puede encontrarse en este Enlace MSE .

Answer 2

Consideremos en primer lugar la ecuación homogénea

$$T(n)=T(\frac n2)+T(\frac n4).$$

Dejar $n=2^k$ ,

$$T(2^k)=T(2^{k-1})+T(2^{k-2)}$$ o $$S(k)=S(k-1)+S(k-2).$$

Deberías reconocer la recurrencia de Fibonacci, con la solución asintótica

$$T(n)=S(k)=O(\phi^k)=O(e^{log(\phi)log(n)/log(2)})=O(n^{0.6942\cdots})$$

Entonces se intenta una solución particular de la ecuación no homogénea, como por ejemplo $T(n)=an^2$ . Introduciendo la ecuación dada,

$$an^2=\frac{an^2}4+\frac{an^2}{16}+n^2$$ y

$$T(n)=\frac{16}{11}n^2$$ funciona.

Como esta solución domina a la otra, se puede concluir $\Theta(n^2)$ .