Cómo simplificar la suma de una relación de recurrencia

Question

Después de resolver la relación de recurrencia

$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$

Obtengo la siguiente ecuación

$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$$

No sé cómo simplificar la suma y cómo saber la función asintótica?

Answer 1

Sea $n=3^k$. Tenemos,

$T(n)=3^kT(\frac{n}{3^k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$

$=3^k.T(1)+n\log\left(n.\frac{n}{3^1}.\frac{n}{3^2}\ldots.\frac{n}{3^k}\right)$

$=3^k.1+n\log\left(n.\frac{n^k}{3^{1+2+\ldots+k}}\right)$ (ya que $T(1)=1$)

$=3^k+n\log\left(\frac{n^{k+1}}{3^{1+2+\ldots+k}}\right)$

$=3^k+n\log\left(\frac{(3^k)^{k+1}}{3^{k(k+1)/2}}\right)$

$=3^k+n\log\left(\frac{3^{k(k+1)}}{3^{k(k+1)/2}}\right)$

$=3^k+3^k\log\left(3^{k(k+1)/2}\right)$

$=3^k+3^k.k(k+1)/2.\log3$

$=3^k+\Theta(3^k.k^2)$

$=\Theta(3^k.k^2)$

$=\Theta(n.(\log n)^2)$ (ya que $n=3^k$)

O usa Teorema maestro:

$T(n) = 3T(\frac{n}{3}) + n\log(n)$, aquí $c_{crit}=\log_b a = \log_3 3 = 1$, $k=1$, por lo tanto, tenemos,

$T(n) = \Theta(n^{c_{crit}}\log^{k+1}n)=\Theta(n\log^2 n)$

Answer 2

Suponiendo $\log n = \ln n$ tenemos

$$ T\left(3^{\log_3 n}\right)=3T\left(3^{\log_3 \left(\frac n3\right)}\right)+n\frac{\log_3 n}{\log_3 e} $$

llamando ahora $\mathcal{T}(\cdot)=T\left(3^{(\cdot)}\right)$ y $z = \log_3 n$ seguimos con la recurrencia

$$ \mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0 $$

con solución

$$ \mathcal{T}(z)= 3^{z-1}c_1+z(z+1)3^z\frac{c_0}{2} $$

y ahora retrocediendo con $z = \log_3 n$ llegamos a

$$ T(n) = \frac n3 c_1 +n(\log_3 n) (1+\log_3 n)\frac {c_0}{2} $$

NOTA

La recurrencia $\mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0 $ es lineal, por lo que la solución se puede componer como $\mathcal{T}(z)=\mathcal{T}_h(z)+\mathcal{T}_p(z)$. La solución homogénea es directa

$$ \mathcal{T}_h(z) = 3^{z-1}c_1 $$

tomando ahora como particular $\mathcal{T}_p(z) = 3^{z-1}c_1(z)$ y sustituyendo en la recurrencia completa obtenemos

$$ c_1(z) = c_1(z-1)+3z c_0 $$

por lo tanto

$$ c_1(z) = \frac 32z(z+1)c_0 $$

etc.