Encuentre la cota superior para T(n) en términos de n y demuéstrelo con el Teorema Maestro

Question

Perdón por el formato. Sólo tenía mi móvil.

Problema : Supongamos que se trata de un algoritmo que se ejecuta en tiempo T(n), donde T(n) es la siguiente relación de recurrencia:

T(n) =

• $2T($$ \frac n3 $$) + (n), x > 2$
• $(1), x 2$

Dibuja un árbol y encuentra el límite superior de T(n) en términos de n. Demuestra el límite superior usando el Teorema Maestro.

Mi solución probada : El árbol de recursión con el que terminé;

Niveles

1. n
2. $$ \frac n3 \frac n3 $$
3. $$ \frac n9 \frac n9 \frac n9 \frac n9 $$
4. .....
5. $$(1) (1) ... (1)$$

Trabajo para cada nivel.

1. n
2. $$ \frac n3 + \frac n3 = \frac 23n$$
3. ...
4. k nodos. Como 2T, tengo $2^k$ con trabajo $$\frac {n}{3^k}$$ que al final sería $$ \left(\frac{2}{3}\right)^kn $$

Dado que existen $$log_3 (n)$$ niveles, terminé con $$n = \frac{n}{1-\frac{2}{3}} = 3n$$

EDIT: que al final sería O(n).

Cuando intento demostrarlo utilizando el Teorema Maestro, no consigo que funcione en ninguno de los 3 casos.

Por ejemplo, para el caso 1: Intento demostrar que T(n) c*n y mi resultado final es T(n) $$\frac 23n + n $$

¿Mi árbol está completamente equivocado o mi comprensión del teorema maestro es errónea?

Agradecería cualquier información, ¡gracias!

Answer 1

Dado que el exponente crítico es $\log_32$ y $f(n)$ es $\Omega(n^{\log_32})$ sólo se aplica el tercer caso (supercrítico) del teorema maestro y tenemos que utilizar la condición de regularidad $$2f(n/3)\le\color{blue}{\frac34}f(n)$$ en $f$ para conseguir que $T(n)=\Theta(n)$ como desee.