n log n est O (n)?

Question

Je tente de résoudre cette récurrence

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

Je suis venu à la solution qu'il appartient aux maîtres théorème 2 cas puisque nlogn est O (n ^ 2)

mais après avoir fait référence au manuel de solution i remarqué cette solution qu'ils ont

Le soluttion dit que n lg n = O (n ^ (lg 3 - e)) pour e entre 0 et 0,58

Cela signifie donc nlogn est O (n) .. est ce droit? Est-ce que je manque quelque chose ici?

est pas NLGN O (n ^ 2)?

Answer 1

This will explain things better

Answer 2

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

Answer 3

n^lg3 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).