$\mathcal{O}(n)$ et $\Omega(n).$

P.2

Je rapporte sur un article ou les deux notations ci dessus sont utilisees. Je connais le classique grand $\mathcal{O}(n)$ mais pas $\Omega(n)$. Que veut dire ce second symbole? Merci a l'avance.

zygomathique

salut

c'est la notation de Hardy ...

voir https://fr.wikipedia.org/wiki/Comparaison_asymptotique#Notation_Ω_de_Hardy_et_Littlewood_(théorie_des_nombres)

noix de totos

Ce symbole $\Omega$ est très présent en théorie analytique des nombres. 

Les définitions du wiki sont parfaitement correctes, on peut toutefois en donner une autre, peut-être plus "imagée" . Soit $f$ une fonction à valeur réelle.

$f(x) = \Omega_+ (g(x))$ signifie qu'il existe $C > 0$ telle que l'inégalité $f(x) > Cg(x)$ a lieu pour une suite $(x_n)_n$ telle que $x_n \to + \infty$.
$f(x) = \Omega_- (g(x))$ signifie qu'il existe $C > 0$ telle que l'inégalité $f(x) < -Cg(x)$ a lieu pour une suite $(x_n)_n$ telle que $x_n \to + \infty$.
$f(x) = \Omega_{\pm} (g(x))$ signifie à la fois $f(x) = \Omega_+ (g(x))$ et $f(x) = \Omega_- (g(x))$.
Enfin, $f(x) = \Omega(g(x)) \iff |f(x)| = \Omega_+(g(x))$.

Exemple. Le problème des diviseurs de Dirichlet est de déterminer l'infimum des réels $\theta \geqslant 0$ tel que $\Delta (x) = O \left( x^{\theta } \right)$ pour $x$ assez grand, où $\Delta(x)$ est le reste dans la formule asymptotique
$$\sum_{n \leqslant x} \tau(n) = x \log x + (2 \gamma-1) x + \Delta(x).$$
Vers 1850, Dirichlet a montré que $\theta \leqslant \frac{1}{2}$, et, au début du 20ème siècle, Voronoï a montré que $\theta \leqslant \frac{1}{3}$. D'un autre côté, Hardy (1916) a montré que $\theta \geqslant \frac{1}{4}$, de sorte que $\Delta(x) = \Omega (x^{1/4})$.

P.2

Merci beaucoup.