Es decir, que $\log_2 n\not\in\Theta(n^x)$ para cualquier $x > 0$
no utilizaré la inducción en $x$ ( como $x = 1$ caso base, etc.)
mi opinión es : uso la def. de big theta:
$$ 0c_1·n^x \le \log_2 n \le c_2· n^x $$
¿a dónde voy a partir de aquí?
Respuesta
¿Demasiados anuncios?
Ok, esto es simple en realidad, demostrar por contradicción:
asumiendo que es cierto, entonces big-theta significa que está entre c1 * $n^x$ y c2 * $n^x$ .
En otras palabras, si tomamos el límite de f(n) / g(n) -debe ser no nulo, finito( no infinito) y debe existir
tomar el límite:
lim (lgn / $n^x$ ) como n -> inf. = lg(inf) / $n^(inf)$ = inf.
lo cual es una contradicción. ¡Hecho!
