Usando el teorema maestro cuando $f(n) = 0$

Question

Estoy tratando de encontrar una solución a la recurrencia $T(n)=3T(\frac{n}{2})$ con el teorema maestro para recurrencias de divide y vencerás, pero no estoy seguro de qué caso puedo aplicar ya que $f(n) = 0$.

Si se puede utilizar el teorema maestro, estoy inclinado hacia $T(n)=\Theta(n^{\log_2{3}})$, ya que $0 \leq n^{\log_2{3}}$. Pero tengo algunas dudas con respecto a algunas definiciones particulares.

1. ¿Es cierto que $0=O(n^{\log_2{3}})$? ¿Cuáles serían los valores de $c$ y $n_0$ tales que $\exists c>0,n_0> 0:f(n) \leq cn^{\log_2{3}}, \forall n \geq n_0$?

2. ¿Es el cero asintóticamente menor que $n^{\log_2{3}}$ por un factor de $n^\epsilon, \epsilon > 0$?

En general, me pregunto si la falta de un $f(n)$ hace que el teorema maestro no sea aplicable y por qué?

Answer 1

Supongo que por $f(n)$, te refieres a que tu relación de recurrencia es de la forma $$ T(n)=aT\left(\frac{n}{b}\right)+f(n), $$ así que en este caso tienes $a=3$, $b=2$ y $f(n)=0$ para todo $n$.

Teniendo en cuenta eso: sí, $f(n)=0$ es perfectamente aceptable.

Para responder a tus preguntas más específicas:

1. Sí, $0=O(n^{\log_2(3)})$. Toma cualquier $n_0\in\mathbb{N}$ y cualquier $c>0$, y es cierto que $0\leq cn^{\log_2(3)}$ para todo $n\geq n_0$. Recuerda, el Big-O solo representa límites superiores asintóticos; por supuesto, algo que tiende a infinito es un límite superior, en el límite, para $0$.

2. Sí, $0$ es 'asintóticamente más pequeño' que $n^{\log_2(3)}$. Toma cualquier $\epsilon\in(0, \log_2(3))$, y es cierto que $0=O(n^{\epsilon})$.

El Teorema Maestro es perfectamente aplicable en esta situación, y muestra que tu $T(n)$ satisface $T(n)=\Theta(n^{\log_2(3)})