Comment prouver ou infirmer que cette fonction est Ω (n^1.5)?

Question

j'ai donc cette fonction récursive: T (n) = T (log (n)) + T (n log (n)) + n

J'ai essayé plusieurs fois le résoudre, mais je n'a pas réussi. (trouver le Thêta) Fondamentalement, il me suffit de prouver ou de réfuter si c'est Omega de n^1,5 (Ω (n^1.5))

Aide sera appréciée, merci d'avance!

tl; dr:

donné T (n) = T (log (n)) + T (n-log (n)) + n

prouver ou à réfuter: T (n) = Ω (n^1,5)

Answer 1

en supposant que T(n) ne devient pas soudainement négatif à une valeur de n, nous pouvons donner une borne inférieure du côté gauche si l'on néglige le premier terme:

Nous définissons une nouvelle fonction S(n) telle que:

On peut voir immédiatement qu'il a termes (en ignorant hors par une etc.). Ainsi, si nous continuons à élargir:

A ce stade, puisque nous savons que log(n) << n pour tout grand n, on peut appliquer une expansion Taylor au troisième terme de l'appel récursif à S(n):

Nous pouvons également ignorer le second terme de manière réaliste. En appliquant cette approximation à chaque appel S(n):

Maintenant, nous savons que:

b peut évidemment être 1.5; donc:

---

EDIT: quelques tests numériques pour confirmer ce résultat -

Code:

uint64_t T(int n) { 
    return n <= 1 ? 0 : T(n - log(n)) + T(log(n)) + (uint64_t)n; 
} 

Résultats:

N   T(N) 
-------------------------- 
2   2 
4   6 
8   18 
16   60 
32   181 
64   578 
128   1911 
256   6331 
512   22011 
1024  79304 
2048  279719 
4096  1016217 
8192  3814210 
16384  13902832 
32768  51540129 
65536  195366441 
131072  732435510 
262144  2744988819 
524288  10457580914 
1048576  39910628826 

Plo t de N^2/log(N) contre T(N):

La relation est linéaire, ce qui signifie que

... confirmant le résultat donné.