Aszimptotikus egyenlőség

Az, hogy az $f(n)$ és a $g(n)$ sorozat aszimptotikusan egyenlő ($f\left({n}\right)\sim g\left({n}\right)$) azt jelenti, hogy $f\left({n}\right)/g\left({n}\right)\rightarrow 1$, ha $n\rightarrow \infty$.

Az aszimptotikus egyenlőség csak a két függvény hányadosáról szól, semmit sem mond a két függvény különbségéről. Így az akár végtelenhez is tarthat.

Becslésre használják a matematika különböző területein.

Példák

Stirling-formula a faktoriális nagyságrendjéről:

$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$

A prímszámok eloszlása:

Jelölje π(x) az 1 és x közötti prímszámok számát. Ekkor:

$\pi (x) \sim \frac{x}{\ln x}$

Az algoritmusok műveletigényét szintén szokás aszimptotikus egyenlőséggel megadni.

Továbbá alkalmazzák például a statisztikában.

Források

• Freud-Gyarmati: Számelmélet
• Algoritmusok műveletigénye
• Statisztikai alkalmazások