¿Se puede resolver $T\left( n\right) = 4T\left({n\over 2}\right) + 2^{n\over2}$ utilizando el método de Akra-Bazzi?

Question

$$T\left( n\right) = 4T\left({n\over 2}\right) + 2^{n\over2}$$

Usando el método de Akra-Bazzi

$a = 4, b = {1\over2}, g(n) = 2^{n\over2}, h(n) = 0$

$$g'(n) = {d\over dx}(2^{n\over2})=2^{{n\over2}-1}\ln 2$$

Dado que $\left|g'(n)\right|$ no está acotado polinómicamente, no podemos proceder con el método de Akra-Bazzi.

Usando el Teorema Maestro

$a = 4, b = 2, g(n) = 2^{n\over 2}$

$g(n) = \Omega(n^{\log_2 4+\epsilon})$ donde $\epsilon=1$, también

$$ag\left( {n\over b}\right) \le cg(n)$$

$$4g\left( {n\over 2}\right) \le cg(n)$$

$$2^{{n\over 4}+2} \le c2^{n\over 2} \tag*{para $c={1\over 2}$ y $n\ge 12$ }$$

Por lo tanto, se sigue del teorema maestro que $T(n) = \Theta\left( g(n)\right) = \Theta\left( 2^{n\over 2}\right)$.

¿Cómo es posible que el problema anterior se pueda resolver usando el Teorema Maestro, que es solo un corolario del método de Akra-Bazzi pero no usando el método de Akra-Bazzi en sí mismo?

Answer 1

Comenzando con $$T(2n)=4T(n)+2^n$$

En este caso, una posibilidad es intentar obtener $U(p)=\sum f(k)$ introduciendo una relación telescópica para $U$: $U(p+1)=U(p)+f(p)$.

Para hacer eso primero establecemos $n=2^p$ para lidiar con la relación $T(2n)$ .vs. $T(n)$.

Y para hacer desaparecer el coeficiente de proporcionalidad $4$ introduciremos el coeficiente $4^p$.

Establezcamos $$T(n)=T(2^p)=4^p\,U(p)$$

La sustitución en la ecuación da:

$\require{cancel}T(2n)=T(2^{p+1})=\cancel{4^{p+1}}U(p+1)=4T(n)+2^n=\cancel{4\cdot 4^p}\,U(p)+2^{2^p}$

Después de agrupar términos de $U$ en un lado y términos de $f$ en el otro:

$U(p+1)-U(p)=2^{2^p}/4^{p+1}=\underbrace{2^{(2^p-2p-2)}}_{f(p)}$

Y puedes sumarlo a $$U(p)=U(0)+\sum\limits_{k=0}^{p-1} 2^{2^k-2k-2}$$

Asintóticamente esta suma es equivalente a su último término $2^{(2^{p-1}-2(p-1)-2)}$ porque $2^{2^k}$ crece muy rápido (usa Cesaro por ejemplo).

Al final $$T(n)\sim 4^p\,2^{(2^{p-1}-2p)}=2^{(2^p/2-2p+2p)}=2^{n/2}$$

Por lo tanto, porque $2^{n/2}$ crece muy rápido tenemos $4T(n/2)\ll T(n)$ y $T(n)$ es solo asintóticamente equivalente a este término en crecimiento.

Answer 2

De

$$T\left(2n\right)=4T\left(n\right)+2^n\Rightarrow T\left(2^{\log_2(2n)}\right)=4T\left(2^{\log_2n}\right)+2^n$$

ahora realizando

$$\mathcal{T}(\cdot) = T\left(2^{(\cdot)}\right),\ \ \ z=\log_2 n$$

tenemos

$$\mathcal{T}(z+1)=4\mathcal{T}(z)+2^{2^z}$$

resolviendo esta recurrencia obtenemos

$$\mathcal{T}(z) = \frac 14 4^z\left(C_0+\sum_{k=0}^{z-1}2^{2^k-2k}\right)$$

o como $4^{\log_2 n} = 2^{2\log_2 n} = 2^{\log_2 n^2} = n^2$

$$T(n) = \frac 14 n^2\left(C_0+\sum_{k=0}^{\log_2 n-1}2^{2^k-2k}\right)$$