¿Cómo se resuelve esta recurrencia?

Question

He estado tratando de practicar las relaciones de recurrencia que pueden ser resueltas por el teorema maestro y me encontré con este .

Ahora el $4^{\textrm{th}}$ problema en ese archivo es :

$$T(n) = 2^n T\left(\frac{n}{2}\right) + n^n.$$

La solución dice que no se puede resolver usando el teorema del Maestro, lo cual es cierto. Pero quiero saber cómo resolverlo.

He intentado pensar en alguna sustitución pero no consigo llegar a ningún sitio ya que la recurrencia contiene términos $2^n$ y $n^n$ ambos. Y si amplío el árbol, se vuelve muy complicado. ¿Alguna solución?

Answer 1

Dejemos que $\begin{cases}k=\log_2n\\U(k)=T(n)\end{cases}$ ,

Entonces $U(k)=2^{2^k}U(k-1)+(2^k)^{2^k}$

$U(k)=2^{2^k}U(k-1)+2^{k\times2^k}$

$U(k+1)=2^{2^{k+1}}U(k)+2^{(k+1)2^{k+1}}$

$\therefore U_c(k+1)=2^{2^{k+1}}U_c(k)$

$U_c(k)=\Theta(k)\prod\limits_k2^{2^{k+1}}$ , donde $\Theta(k)$ es una función periódica arbitraria con período unitario

Según http://en.wikipedia.org/wiki/Indefinite_product#Rules ,

$U_c(k)=\Theta(k)2^{\sum\limits_k2^{k+1}}$ , donde $\Theta(k)$ es una función periódica arbitraria con período unitario

Según http://en.wikipedia.org/wiki/Indefinite_sum#Antidifferences_of_exponential_functions ,

$U_c(k)=\Theta(k)2^{2^{k+1}}$ , donde $\Theta(k)$ es una función periódica arbitraria con período unitario

Dejemos que $U(k)=2^{2^{k+1}}V(k)$ ,

Entonces $2^{2^{k+2}}V(k+1)=2^{2^{k+1}}2^{2^{k+1}}V(k)+2^{(k+1)2^{k+1}}$

$2^{2^{k+2}}V(k+1)=2^{2^{k+2}}V(k)+2^{(k+1)2^{k+1}}$

$V(k+1)=V(k)+2^{(k-1)2^{k+1}}$

$V(k)=\Theta(k)+\sum\limits_k2^{(k-1)2^{k+1}}$ , donde $\Theta(k)$ es una función periódica arbitraria con período unitario

$U(k)=\Theta(k)2^{2^{k+1}}+2^{2^{k+1}}\sum\limits_k2^{(k-1)2^{k+1}}$ , donde $\Theta(k)$ es una función periódica arbitraria con período unitario

$T(n)=\Theta(\log_2n)4^n+4^n\left(\sum\limits_k2^{(k-1)2^{k+1}}\right)_{k\to\log_2n}$ , donde $\Theta(n)$ es una función periódica arbitraria con período unitario

Answer 2

Presentación de $U(n)=T(n)/4^n$ se ve que $U(n/2)=T(n/2)/2^n$ por lo que la recursión sobre $(T(n))_n$ produce $U(n)=U(n/2)+(n/4)^n$ .

A grandes rasgos, esto significa que $U(n)=(n/4)^n+(n/8)^{n/2}+(n/16)^{n/4}+\ldots$ De forma más rigurosa, el $\ldots$ esconde como máximo $\log_2n$ plazos, cada uno de ellos inferior a $(n/8)^{n/2}$ Por lo tanto $$ (n/4)^n\leqslant U(n)\leqslant(n/4)^n+\log_2(n)\cdot(n/8)^{n/2}, $$ lo que implica $$ n^n\leqslant T(n)\leqslant n^n+\log_2(n)\cdot(2n)^{n/2}. $$ Desde $\log_2(n)\cdot(2n)^{n/2}\ll n^n$ esto da como resultado $\lim\limits_{n\to\infty}T(n)/n^n=1$ Por lo tanto $T(n)=\Theta(n^n)$ .

Answer 3

Sugerencia: si $k = T(n)/n^n$ entonces $$T(2n) = k 2^{2n}n^n +(2n)^{2n} = \left(k/n^n+1\right) (2n)^{2n}$$