$T(n)=3T(n/2) + n\log n,\ T(1)=1$

Question

Posible duplicado:
$T(n) = 4T({n/2}) + \theta(n\log{n})$ utilizando el Teorema Maestro

¿Cuál es el orden de esta recurrencia?

$$T(n)=3T(n/2) + n\log n,\ \ T(1)=1$$

Encontré la respuesta donde $a=2$ utilizando el caso 2 del Teorema Maestro, pero no pudo hacerlo funcionar para $a=3$ .

Answer 1

Hay que utilizar el caso 1 del teorema maestro, que dice que si $$ T(n)=aT(n/b)+f(n),\qquad a\ge 1, \ b>1, \qquad (1)$$ y $$f(n)=O(n^{(\log_b a)-\epsilon}), \qquad \epsilon>0,\qquad (2)$$ entonces $$T(n)=\Theta(n^{\log_b a}). \qquad (3)$$ (Además, algunas suposiciones sobre la forma de redondear $n/b$ y la positividad de $T$ y $f$ son necesarios).

En este caso, $a=3$ y $b=2$ Así que $\log_b a =\log_2 3 > 1$ . Desde $f(n)=n\log n$ tenemos $f(n)=O(n^{1+\delta})$ para cualquier $\delta>0$ . Ahora toma $\delta=\epsilon=((\log_b a)-1)/2$ para comprobar que (2) se cumple. Entonces, por (3), $T(n)=\Theta(n^{\log_2 3}).$

Para encontrar el orden de $T(n)$ sin usar el teorema maestro, puedes hacer lo siguiente:

• Encontrar una constante $\epsilon>0$ tal que, si $2^m\le n\le 2^{m+1}$ y $m\ge 0$ entonces $T(n)\ge \epsilon 3^m$ . A continuación, demuestre por inducción que esto es cierto para todo $m\ge 0$ . Esto demuestra que $T(n)=\Omega(n^{\log_2 3}).$

• Encontrar constantes $K>0$ , $L>0$ y $M\ge 0$ tal que, si $2^m\le n\le 2^{m+1}$ y $m\ge M$ entonces $T(n)\le K 3^m - L m 2^m $ . A continuación, demuestre por inducción que esto es cierto para todo $m\ge M$ . Esto demuestra que $T(n)=O(n^{\log_2 3}).$

En conjunto, esto demuestra que $T(n)=\Theta(n^{\log_2 3}).$

Answer 2

Sea $R(k)=T(2^k)$ . Entonces $R(k)=3R(k-1)+k2^k\log 2$ . Así que $$R(k)=3^{k-1} + \sum_{i=2}^{k} 3^{k-i}i2^i\log 2 = 3^{k-1} + 3^k\log 2\sum_{i=2}^k i\left(\frac 2 3\right)^i$$ .

Desde $\sum_{i=2}^\infty i\left(\frac 2 3\right)^i$ converge, $R(k)$ es esencialmente exponencial con base $3$ .

Ahora usa eso $T(n)=R(\log_2 n)$ .

Por lo tanto, hay $c_0,c_1$ tal que para $n>4$ , $$c_0 3^{\log_2{n}}<T(n) < c_1 3^{\log_2 n} $$ . Escribir $3=2^{\log_3{2}}$ podemos verlo:

$$c_0n^{\log_3 2}< T(n) < c_1n^{\log_3 2}$$