Resolver la relación de recurrencia $T(n)=4T(n/3) + n$, $T(3) = 1$, $n = 3^k$ luego determine los límites superiores e inferiores

Question

Me gustaría resolver la siguiente relación de recurrencia. Después de eso debo encontrar sus límites superior e inferior.

$T(n)=4T(\frac{n}{3})+n, T(3)=1, n = 3^k$

Intenté resolver con sustitución:

k = 1: $T(n)=4T(\frac{n}{3})+n$
k = 2: $T(n)=4^2T(\frac{n}{3^2})+\frac{4n}{3}+n$
k = 3: $T(n)=4^3T(\frac{n}{3^3})+\frac{4^2n}{3^2}+\frac{4n}{3}+n

General: $T(n)=4^kT(\frac{n}{3^k})+\sum_{i=1}^k(\frac{4^{i-1}}{3^{i-1}})n=4^kT(\frac{3^k}{3^k})+...=4^kT(1)+...

Q1: Aquí es donde llegó mi primer problema; no se me dio una relación para T(1) así que no puedo terminar con la sustitución, ¿verdad? ¿Tal vez mi profesor cometió un error tipográfico y quiso poner T(1) = 1?

Suponiendo que él no cometió un error tipográfico, decidí intentar resolver el problema usando el Teorema Maestro:

Teorema Maestro: $T(n)=aT(\frac{n}{b})+n^d$ donde $a,b > 0$ y $d\ge0$ entonces

$T(n)=\Theta(n^d)$ si $d>\log_b(a)$
$T(n)=\Theta(n^d\log(n))$ si $d=\log_b(a)$
$T(n)=\Theta(n^{\log_b(a)})$ si $d<\log_b(a)

Usando este método obtengo $T(n)=\Theta(n^{1.262})

Q2: Leí que $\Theta(g(n))$ es tanto el límite superior $O(g(n))$ como el límite inferior $\Omega(g(n)) entonces eso significa que las tres respuestas a mi pregunta serían...

Solución a la relación de recurrencia: $T(n)=\Theta(n^{1.262})
Límite superior: $O(n^{1.262})
Límite inferior: $\Omega(n^{1.262})

Answer 1

P1: Aquí es donde llegó mi primer problema; no me dieron una relación para T(1) así que no puedo terminar con la sustitución, ¿verdad? ¿Quizás mi profesor cometió un error tipográfico y quiso poner T(1) = 1?

No, tu profesor estaba correcto al proporcionar $T(3) = 1$, dado $n = 3^{k}$. Como probablemente notaste al usar el método de sustitución, generalmente hay una relación en la potencia del coeficiente - en este caso, $4 - y la potencia del denominador en T(). Al darte cuenta de esto, a menudo puedes generalizar rápidamente y pasar a la condición base. Para ilustrarlo explícitamente:

\begin{align} T(n) &= 4^{1}T(\frac{n}{3^{1}}) + n \\ &= 4^{2}T(\frac{n}{3^{2}}) + 4n + n \\ &= 4^{3}T(\frac{n}{3^{3}}) + 4^{2}n + 4n + n \\ & = \ ... \end{align}

En este punto, mira el valor dentro de T() para determinar el número restante de sustituciones adicionales que deben tener lugar. Para este problema, el caso base es $T(3) = 1$, y,

$$3 = \frac{n}{3^{k-1}}$$

por lo tanto, obtenemos

\begin{align} T(n) &= 4^{k-1}T(\frac{n}{3^{k-1}}) + 4^{k-2}n + ... + 4^{k - (k - 1)}n + n \\ & = 4^{k-1} + 4^{k-2}n + ... + 4^{k - (k - 1)}n + n \end{align}

Ahora, estos términos deben sumarse. Reexpresando $4 = 2^{2}$ y factorizando n,

\begin{align} T(n) & = 2^{2(k-1)} + 2^{2(k-2)}n + ... + 2^{2(k - [k - 1])}n + n \\ & = 2^{2(k-1)} + n(2^{2(k-2)} + ... + 2^{2(k - [k - 1])} + 1) \end{align}

Reconociendo que los términos entre paréntesis representan colectivamente una serie geométrica, podemos sumar fácilmente los términos para obtener

\begin{align} T(n) &= 2^{2(k-1)} + n\sum_{i=1}^{k-2} \ (2^{2})^{i} \\ &= 2^{2(k-1)} + n(2^{2(k-2)+1} - 1)\end{align}

Finalmente, sustituye $k$ nuevamente para obtener

\begin{align} T(n) &= 4^{(log_{3}(n)-1)} + n(4^{(log_{3}(n)-2)+1} - 1) \\ &= 4^{log_{3}(n)-1}(n+1)-n \end{align}

P2: He leído que Θ(g(n)) es tanto el límite superior O(g(n)) como el límite inferior Ω(g(n)), así que eso significa que las tres respuestas a mi pregunta serían...

Usando el caso 1 del Teorema Maestro como se describe aquí, $T(n) \in \Theta(n^{1.262})$. El uso de la notación theta sola será suficiente para describir los límites de esta función, ya que se implica en su definición. Considera el siguiente gráfico: