n log n es O (n)?

Question

Estoy intentando solucionar esta recurrencia

T (n)= 3 T (n / 2) + n lg n ..

He llegado a la solución de que pertenece al caso 2 del teorema de los maestros ya que n lg n es O (n ^ 2)

pero después de consultar el manual de la solución, noté esta solución que tienen

La solución dice que n lg n= O (n ^ (lg 3 - e)) para e entre 0 y 0.58

entonces esto significa que n lg n es O (n) ... ¿es así?¿Me falta algo aquí?

¿No es nlgn O (n ^ 2)?

Answer 1

Esto explicará mejor las cosas

Answer 2

n*log(n) no es O(n^2).Se conoce como cuasi-lineal y crece mucho más lento que O(n^2).De hecho, n*log(n) es menor que un polinomio.

En otras palabras:

O(n*log(n)) < O(n^k)

donde k > 1

En su ejemplo:

3*T(2n) -> O(n^1.585)

Dado que O(n^1.585) es polinomio y domina O(n*log(n)), el último término desaparece por lo que la complejidad final es solo O(n^1.585).

Answer 3

n ^lg3 no es O (n).Supera O (n) ... De hecho, cualquier exponente en n que sea mayor que 1 da como resultado un tiempo asintóticamente más largo que O (n).Dado que lg (3) es aproximadamente 1,58, siempre que restes menos de 0,58 del exponente, es asintóticamente mayor que O (n).