Método de sustitución por recurrencia

Question

Sólo quiero ver si lo hice bien. Necesito demostrar que $T(n) = 3T(n/4) + n\log n$ muestra que $T(n) = O(n\log n)$ utilizando el método de sustitución en recurrencia.

$$T(n) = 3c(n/4 \log n/4) + n\log n$$ $$c\log nn - cn + n\log n$$ $$n\log n$$ No me parece correcto pero he seguido un ejemplo y así me ha salido. Gracias por cualquier ayuda con esto.

Answer 1

Supongamos que $T(m) < c m \log m $ para $m < n$ (esto se denomina inducción fuerte ya que depende de todos los valores precedentes, no sólo del valor inmediatamente anterior).

Entonces

$\begin{align} T(n) &= 3 T(n/4) + n \log n\\ &< 3 c (n/4) \log(n/4) + n \log n\\ &= 3 c (n/4) (\log(n)-\log(4)) + n \log n\\ &= (3 c n/4) \log(n)-(3 c n/4) \log(4) + n \log n\\ &< (3 c/4+1) n \log(n)\\ \end{align} $

Si $3 c/4+1 < c$ , entonces $T(n) < c n \log n$ . Esto es cierto si $c > 4$ .

Así que.., una vez que encontremos un $c > 4$ tal que $T(n) < c n \log n$ para algunos valores iniciales de $n$ , entonces $T(n) < c n \log n$ para todos los valores mayores de $n$ .

Para ello, sólo tiene que elegir cualquier $c > \max(4, T(2)/(2 \log 2), T(3)/(3 \log 3)) $ .

Entonces $T(n) < c n \log n$ para todos $n$ , así que $T(n) = O(n \log n)$ .

Answer 2

$$T(n) \in O(n \log n)$$ se define como $$(\exists C>0, n_0>0)(\forall n > n_o)\, T(n) \le C \cdot n \log n$$

Dado que $T(n) = 3\,T\left(\frac n4\right) + n \log n$ tenemos que encontrar $C$ y $n_0$ para satisfacer la definición. Procedamos inductivamente:

$$T(n) \le C \cdot n \log n$$ $$3\,T\left(\frac n4\right) + n \log n \le C \cdot n \log n$$

Ahora vemos que necesitamos tomar prestada la hipótesis inductiva $T\left(\frac n4\right) \le C \cdot \frac n4 \log \frac n4$ . Por lo tanto, la afirmación anterior estaría implícita en:

$$3\,\left(C \cdot \frac n4 \log \frac n4\right) + n \log n \le C \cdot n \log n$$

Así que ahora si podemos encontrar un positivo $C$ que hace cierta la afirmación anterior para valores positivos suficientemente grandes $n$ entonces hemos satisfecho la definición deseada. Mueve un poco las cosas:

$$3~C~n~\log n - 3~C~n~\log 4 + 4~n~\log n \le 4~C~n~\log n$$

$$4 \le \frac{3~C~\log 4} {\log n } + C$$

$$\frac{4 \log ~ n}{\log n + 3~\log(4)} \le C$$

Podemos ver que el lado izquierdo nunca será tan grande como $4$ (dejar $n = 4^z$ y simplificar para que quede más claro), así que $C \ge 4$ satisface la desigualdad para un valor suficientemente grande de $n$ .

Answer 3

¿Te parece bien?

$$\begin{align*}T(n) &= 3T\left(\frac{n}{4}\right)+n \log n T\left(\frac{n}{4}\right) \\ & = 3T\left(\frac{n}{16}\right)+\frac{n}{4} \log\left(\frac{n}{4}\right) T(n) \\ & = 3\left[3T\left(\frac{n}{16}\right)+\frac{n}{4} log\left(\frac{n}{4}\right)\right]+n\log n \\ & = 9T\left(\frac{n}{16}\right) + \frac{3n}{4}log\left(\frac{n}{4}\right)+n\log n \\ & \lt 9T\left(\frac{n}{16}\right) + \left(\frac{3n}{4}\right) \log n + n \log n \\ & = 9T\left(\frac{n}{16}\right) + \left(\frac{7n}{4}\right) \log n \end{align*}$$

que luego termina como $n\log n$ ¿Verdad?