Estou tentando resolver essa recorrência

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

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

mas depois de me referir ao manual da solução, notei 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) .. isso está certo? Estou faltando alguma coisa aqui?

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