n log n is O(n)?

algorithm recurrence
Wael Awada picture Wael Awada · Oct 20, 2011 · Viewed 72.5k times · Source

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

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) ?

Answer

Sreenath Nannat picture Sreenath Nannat · Oct 20, 2011

This will explain things better enter image description here

Related questions

What's the best way to model recurring events in a calendar application?

I'm building a group calendar application that needs to support recurring events, but all the solutions I've come up with to handle these events seem like a hack. I can limit how far ahead one can look, and then generate …

Read More
Solving T(n) = 4T(n/2)+n²

I am trying to solve a recurrence using substitution method. The recurrence relation is: T(n) = 4T(n/2)+n2 My guess is T(n) is Θ(nlogn) (and i am sure about it because of master theorem), and to find an …

Read More
how to write a recurrence relation for a given piece of code

In my algorithm and data structures class we were given a few recurrence relations either to solve or that we can see the complexity of an algorithm. At first, I thought that the mere purpose of these relations is to …

Read More