n log n é O (n)?

Question

Estou tentando resolver esta recorrência

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

Cheguei à solução de que ele pertence ao caso 2 do teorema de mestre, uma vez que n lg n é O (n ^ 2)

mas depois de consultar o manual da solução, percebi esta solução que eles têm

A solução diz que n lg n= O (n ^ (lg 3 - e)) para e entre 0 e 0,58

então isso significa que n lg n é O (n) .. está certo?Estou perdendo alguma coisa aqui?

Não é nlgn O (n ^ 2)?

Answer 1

Isso explicará as coisas melhor

Answer 2

n*log(n) não é O(n^2).É conhecido como quase linear e cresce muito mais lentamente do que O(n^2).Na verdade, n*log(n) é menor que polinomial.

Em outras palavras:

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

onde k > 1

No seu exemplo:

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

Uma vez que O(n^1.585) é polinomial e domina O(n*log(n)), o último termo diminui, então a complexidade final é apenas O(n^1.585).

Answer 3

n ^lg3 não é O (n).Ele supera O (n) ... Na verdade, qualquer expoente em n maior que 1 resulta em um tempo assintoticamente mais longo do que O (n).Uma vez que lg (3) é cerca de 1,58, contanto que você subtraia menos de 0,58 do expoente, ele é assintoticamente maior que O (n).