n log n è O (n)?

Question

Sto cercando di risolvere questa ricorrenza

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

Sono giunto alla soluzione che appartiene al caso 2 del teorema dei maestri poiché n lg n è O (n ^ 2)

ma dopo aver fatto riferimento al manuale della soluzione ho notato questa soluzione che hanno

La soluzione dice che n lg n= O (n ^ (lg 3 - e)) per e compreso tra 0 e 0,58

quindi questo significa che n lg n è O (n) .. è giusto?Mi manca qualcosa qui?

Non è nlgn O (n ^ 2)?

Answer 1

Questo spiegherà le cose meglio

Answer 2

n*log(n) non è O(n^2).È noto come quasi-lineare e cresce molto più lentamente del O(n^2).In effetti n*log(n) è minore di polinomio.

In altre parole:

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

dove k > 1

Nel tuo esempio:

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

Poiché O(n^1.585) è polinomiale e domina O(n*log(n)), quest'ultimo termine si riduce, quindi la complessità finale è solo O(n^1.585).

Answer 3

n ^lg3 non è O (n).Supera O (n) ... In effetti, qualsiasi esponente su n maggiore di 1 risulta in un tempo asintoticamente più lungo di O (n).Poiché lg (3) è circa 1,58, fintanto che sottrai meno di .58 dall'esponente è asintoticamente maggiore di O (n).