algorithm - big - n log n es O(n)?

log n graph

Question

Estoy tratando de resolver esta recurrencia.

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

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

pero después de consultar el manual de soluciones, me di cuenta de 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

así que esto significa que n lg n es O (n) ... ¿es esto correcto? ¿Me estoy perdiendo de algo?

¿No es nlgn O (n ^ 2)?

Answer 1

Esto explicará mejor las cosas.

Answer 2

n ^lg3 no es O (n). Vence a O (n) ... De hecho, cualquier exponente en n que sea mayor que 1 resulta en un tiempo asintóticamente más largo que O (n). Como lg (3) es aproximadamente 1.58, siempre que restes menos de .58 del exponente, es asintóticamente mayor que O (n).

Answer 3

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 el polinomio.

En otras palabras:

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

donde k > 1

En tu ejemplo:

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

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