Resolver recurrencias de la forma $T(n)=aT(n/a)+Θ(nlgn)$

Question

En las páginas 95 y 96 de la tercera edición del libro CLRS, encontramos lo siguiente, que se aplica aquí ya que $a=b$ es todo lo que que se necesita para bloquear la aplicación del Teorema Maestro: "Aunque $n\lg n$ es asintóticamente mayor que n, no es polinómicamente mayor porque el cociente $\tfrac{n\lg n}{n}=\lg n$ es asintóticamente menos que $n^{\epsilon}$ para cualquier constante positiva $\epsilon$ . En consecuencia, la recurrencia cae en el hueco entre el caso 2 y el caso 3". Para la solución, los autores nos remiten al ejercicio 4.6.2 de la página 106:

"Demostrar que si $f\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k}n\right)$ , donde $k\geq0$ entonces la recurrencia maestra tiene solución $T\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k+1}n\right)$ . Para simplificar, limite su análisis a las potencias exactas de b".

(Aquí $\lg^k n$ es la notación de CLRS para $(\log_2 n)^k$ .)

Aquí es donde estoy empezando a tener problemas...

Answer 1

Dado que esta pregunta se hace con frecuencia, intentaré elaborar una solución para enteros positivos genéricos $a$ donde $a\ge 2$ .

Supongamos que tenemos $T(0)=0$ y $$T(1)=T(2)=\ldots =T(a-1)=1$$ y para $n\ge a$ $$T(n) = a T(\lfloor n/a \rfloor) + n \lfloor \log_a n \rfloor.$$

Además, deja que la base $a$ representación de $n$ sea $$n = \sum_{k=0}^{\lfloor \log_a n \rfloor} d_k a^k.$$

Entonces podemos desenrollar la recurrencia para obtener lo siguiente exactamente fórmula para $n\ge a$ $$T(n) = a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_a n \rfloor} d_k a^{k-j}.$$

Ahora, para obtener un límite superior, considere una cadena formada por el dígito $a-1$ para obtener $$T(n) \le a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_a n \rfloor} (a-1) \times a^{k-j}.$$

Esto se simplifica a $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times (a-1) \sum_{k=0}^{\lfloor \log_a n \rfloor-j} a^k$$ que es $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) (a^{\lfloor \log_a n \rfloor + 1 -j} -1)$$ que se convierte en $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j) (a^{\lfloor \log_a n \rfloor + 1} - a^j).$$ La suma produce cuatro términos.

La primera es $$\lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor + 1}.$$ El segundo es $$- \lfloor \log_a n \rfloor \frac{a^{\lfloor \log_a n \rfloor}-1}{a-1}.$$ La tercera es $$- \frac{1}{2} a^{\lfloor \log_a n \rfloor + 1} (\lfloor \log_a n \rfloor -1) \lfloor \log_a n \rfloor$$ y el cuarto es $$\frac{1}{(a-1)^2} \left(a + a^{\lfloor \log_a n \rfloor} (\lfloor \log_a n \rfloor (a-1) -a)\right).$$

Este límite representado por estos cuatro términos más el término principal se se alcanza realmente y no se puede mejorar. Para la asintótica sólo necesitamos sólo necesitamos el término dominante, que es $$\left(a - \frac{1}{2} a \right) \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor} = \frac{1}{2} a \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$

Ahora para el límite inferior, que se produce con un dígito de uno seguido de ceros para dar $$T(n) \ge a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times a^{\lfloor \log_a n \rfloor-j}.$$ Esto se simplifica a $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j) \times a^{\lfloor \log_a n \rfloor}$$ que es $$a^{\lfloor \log_a n \rfloor} + a^{\lfloor \log_a n \rfloor} \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j)$$ que finalmente produce $$a^{\lfloor \log_a n \rfloor} + a^{\lfloor \log_a n \rfloor} \sum_{j=1}^{\lfloor \log_a n \rfloor} j$$ o $$a^{\lfloor \log_a n \rfloor} + \frac{1}{2} \lfloor \log_a n \rfloor (\lfloor \log_a n \rfloor +1) a^{\lfloor \log_a n \rfloor}.$$ El término dominante aquí es $$\frac{1}{2} \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$

Uniendo los términos dominantes de la cota superior y de la cota inferior obtenemos la asintótica $$\color{#00A}{\lfloor \log_a n \rfloor^2 \times a^{\lfloor \log_a n \rfloor} \in \Theta\left((\log_a n)^2 \times a^{\log_a n}\right) = \Theta\left((\log n)^2 \times n\right)}.$$

Este Enlace MSE tiene una serie de cálculos similares.

Answer 2

Esto es susceptible de ser analizado por el método Akra-Bazzi. Los cálculos son los siguientes, utilizando la notación del artículo de Wikipedia:

\begin{eqnarray*} k & = & 1 \\ a_1 & = & a \\ b_1 & = & 1/a \\ g(x) & = & x \log x \\ h(x) & = & 0 \\ p & = & 1 \Leftarrow a_1 b_1=1 \\ T(x) & = & \Theta \left ( x \left ( 1 + \int_1^x \frac{u \log u}{u^{p+1}} du \right ) \right ) \\ & = & \Theta \left ( x \left ( 1 + \Theta \left (\log(x)^2 \right ) \right ) \right ) \\ & = & \Theta \left ( x \log(x)^2 \right ) \end{eqnarray*} Es posible que esto no le ayude mucho, ya que no podrá demostrar que el método Akra-Bazzi funciona.