Ayuda para resolver las series de suma de una función recursiva

Question

Ayer en clase estuvimos analizando el algoritmo de multiplicación de Karatsuba y cómo se aplica a las ecuaciones de recurrencia. El tiempo se agotó, y creo que me perdí cómo resolver la suma final.

En primer lugar, definimos la ecuación de recurrencia como

$$T(n) = 3T \left(\frac{n}{2}\right) + 4n$$

y aplicar un árbol de recurrencia como

$$T(n) = 3T \left(\frac{n}{2}\right) + 4n \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^0$$

$$T\left(\frac{n}{2}\right) = 3T \left (\frac{n}{4} \right) + 4\left(\frac{n}{2}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^1$$

$$T\left(\frac{n}{4}\right) = 3T \left (\frac{n}{8} \right) + 4\left(\frac{n}{4}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^2$$

$$T\left(\frac{n}{8}\right) = 3T \left (\frac{n}{16} \right) + 4\left(\frac{n}{8}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^3$$

Como el denominador aumenta de forma logarítmica, definimos el sumatorio como

$$\sum_{x=0}^{log_2n} 4n \cdot \left(\frac{3}{2}\right)^x$$

El tiempo era escaso, así que se saltaron varios pasos, y la solución final se dio como

$$9\cdot 3^{log_2n} = 9n^{log_23} = 9n^{1.58} = O(n^{1.58})$$

en función de las propiedades

$$a^{lg\, b} = b^{lg\, a}\: \text{and}\: log_2 3 \approx 1.58$$

He intentado aplicar la fórmula de la suma

$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1}$$

con este resultado, y terminar con

$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1} = \sum_{x=0}^{log_2 n} 4n \cdot \left(\frac{3}{2}\right)^x $$

$$= 4\left(n\cdot \frac{\frac{3}{2}^{lg_2n+1}-1}{\frac{3}{2}-1}\right) = 4\left(n \cdot \frac{\frac{3}{2}^{log_2n+1}-1}{\frac{1}{2}}\right) = 2\left(n \cdot \frac{3}{2}^{log_2n+1}+1\right) $$

$$=2n \cdot 3^{log_2n+1} + 2$$

que es muy diferente a la solución dada. ¿En qué me he equivocado?

Answer 1

El error crucial es que usted pasó de alguna manera de $$ (\frac32)^{(\log_2 n) +1} $$ a $$ 3^{(\log_2 n )+ 1}. $$ Utilizando la fórmula aproximada que $$ \sum_{x=0}^n r^x = O(r^n) \qquad \qquad\text{if $ r>1 $}, $$ debes conseguir $$ O(n (\frac32)^{\log_2 n})=O(n e^{(\ln n) \frac{\ln \frac32}{\ln 2}}) = O(n^{1+\frac{\ln \frac32}{\ln 2}}). $$ Desde $$ 1 + \frac{\ln \frac32}{\ln 2} = \frac{\ln 3}{\ln 2} = \log_2 3 = 1.58496... $$ este es el mismo resultado que obtuviste en clase.

Answer 2

Esta recurrencia tiene la agradable propiedad de que podemos calcular valores explícitos para $T(n)$ de la misma manera que se hizo aquí por ejemplo.

Dejemos que $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ sea la representación en dígitos binarios de $n.$ No es difícil ver que con $T(0)=0$ tenemos $$ T(n) = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 3^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Ahora, para un límite superior, considere $n$ compuesto sólo por un dígito, lo que da $$ T(n) \le 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j \left( 2^{\lfloor \log_2 n \rfloor + 1} - 2^j\right) $$ que es $$ 4 \left( 2^{\lfloor \log_2 n \rfloor + 1} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} - \sum_{j=0}^{\lfloor \log_2 n \rfloor}3^j \right) = 4 \left(2 \left( 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 1}\right) - \frac{3^{\lfloor \log_2 n \rfloor + 1}-1}{3-1} \right) = 2\times 3^{\lfloor \log_2 n \rfloor + 2} - 2^{\lfloor \log_2 n \rfloor + 4} + 2.$$ Para un límite inferior, tome todos los dígitos cero excepto el primero, obteniendo $$ T(n) \ge 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j 2^{\lfloor \log_2 n \rfloor} = 2^{\lfloor \log_2 n \rfloor + 2} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} = 4\times 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 3} .$$ El límite inferior y el límite superior tomados conjuntamente muestran que $$ T(n) \in \Theta\left(3^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2 3 \lfloor \log_2 n \rfloor} \right) = \Theta\left(n^{\log_2 3}\right).$$