n log n is O(N) ?
I am trying to solve this recurrence

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

I have come to the solution that it belongs to masters theorem case 2 since n lg n  is O(n^2)

but after referring to the solution manual i noticed this solution that they have

![enter image description here][1]


  [1]: http://i.stack.imgur.com/GRtZd.jpg


The soluttion  says that n lg n = O ( n ^(lg 3 - e)) for e between 0 and 0.58

so this means n lg n is O(n) .. is this right? Am i missing something here?

Isn't nlgn O(n^2) ?

Thanks


n log n is O(N) ?
===

I am trying to solve this recurrence

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

I have come to the solution that it belongs to masters theorem case 2 since n lg n  is O(n^2)

but after referring to the solution manual i noticed this solution that they have

![enter image description here][1]


  [1]: http://i.stack.imgur.com/GRtZd.jpg


The soluttion  says that n lg n = O ( n ^(lg 3 - e)) for e between 0 and 0.58

so this means n lg n is O(n) .. is this right? Am i missing something here?

Isn't nlgn O(n^2) ?

Thanks

