Es $n\log n = \Omega (n^{log_4(3) + \varepsilon})$ ?

Question

Estoy leyendo CLRS (Introducción a los algoritmos). Lo siguiente en un ejemplo de cómo utilizar el teorema maestro para determinar la complejidad de una recurrencia.

$$T(n) = 3T\left(\frac{n}{4}\right) + n\log .$$

con $a = 3, b = 4.$

$$f(n) = n\log n.$$

$$n^{\log_b(a)} = n(\log_4(3)) = O(n^{0.793})$$

La siguiente afirmación es lo que no entiendo.

Desde $$f(n) = \Omega(n^{log_4(3) + \epsilon})$$ donde $\varepsilon 0.2$ Caso $3$ se aplica.

¿De dónde ha salido ese (^)?

Answer 1

$3<4$ Así que $\log_4(3)<1$ Así que hay un pequeño $\epsilon$ tal que $\log_4(3)+\epsilon<1$ . Esto implica $n^{\log_4(3)+\epsilon} < n^1 < n\log n$ para valores suficientemente grandes de $n$ .