CODEWITHSUNDEEP
algorithmrecurrence
Wael Awada
Wael Awada

Reputation: 1526

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

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

Upvotes: 27

Views: 96273

Answers (3)

Sreenath Nannat
Sreenath Nannat

Reputation: 2019

This will explain things better enter image description here

Upvotes: 100

Mysticial
Mysticial

Reputation: 471229

n*log(n) is not O(n^2). It's known as quasi-linear and it grows much slower than O(n^2). In fact n*log(n) is less than polynomial.

In other words:

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

where k > 1

In your example:

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

Since O(n^1.585) is polynomial and dominates O(n*log(n)), the latter term drops off so the final complexity is just O(n^1.585).

Upvotes: 15

user684934
user684934

Reputation:

nlg3 is not O(n). It outgrows O(n)... In fact, any exponent on n that is larger than 1 results in an asymptotically longer time than O(n). Since lg(3) is about 1.58, as long as you subtract less than .58 from the exponent it is asymptotically greater than O(n).

Upvotes: 6

Related Questions