Matematyka.pl

Poniżej znajdują się definicję notacji "małe o" i "duże O" przy założeniu, że funkcji \(\displaystyle{ f}\) i \(\displaystyle{ g}\) są określone w sąsiedztwie punktu \(\displaystyle{ a}\).

Gdy \(\displaystyle{ x \to a, \; a \in \mathbb{R} \cup \{ \pm \infty \}}\), to \(\displaystyle{ f(x) = o ( g(x) ) \iff \lim_{x \to a} \frac{f(x)}{g(x)} = 0}\)

Gdy \(\displaystyle{ x \to a, \; a \in \mathbb{R} \cup \{ \pm \infty \}}\), to \(\displaystyle{ f(x) = \mathcal{O} ( g(x) ) \iff \exists \, C, \delta \in \mathbb{R}: |f(x)| \le \, C | g(x) | \; \; \text{dla} \; |x - a| < \delta}\)

O ile w prostych przypadkach arytmetyka na notacji "duże O" (analogicznie dla notacji "małe o") jest intuicyjna, jak np.:

• \(\displaystyle{ \mathcal{O} (f(x)) + \mathcal{O} (g(x)) = \mathcal{O} ( \max \{ f(x), g(x) \} )}\)
• \(\displaystyle{ \mathcal{O} (f(x)) \cdot \mathcal{O} (g(x)) = \mathcal{O} ( f(x) g(x))}\)
• \(\displaystyle{ k \cdot \mathcal{O} ( f(x)) = \mathcal{O} ( f(x)) , \quad k = \text{const}}\)

o tyle w ogólności należy być bardzo ostrożnym gdyż np. uproszczenie \(\displaystyle{ \exp \left( \ln \mathcal{O} (f(x)) \right)}\) do \(\displaystyle{ \mathcal{O} (f(x))}\) nie jest zdefiniowane.



Przykłady

• Dla \(\displaystyle{ 0 \le k < n}\), gdy \(\displaystyle{ x \to +\infty}\) jest \(\displaystyle{ x^k = o ( x^n )}\) a także \(\displaystyle{ x^n = \mathcal{O} (x^n)}\), gdyż:
  \(\displaystyle{ \lim_{x \to + \infty} \frac{x^k}{x^n} = \lim_{x \to + \infty} x^{k - n} = 0}\)oraz \(\displaystyle{ |x^n| \le |x^n|}\)
• \(\displaystyle{ \sin x = \mathcal{O} (1)}\), gdy \(\displaystyle{ x \to + \infty}\), ponieważ:\(\displaystyle{ |\sin x| \le 1}\) - funkcja jest ograniczona.
• \(\displaystyle{ \sin x = x + o(x)}\) (możliwe jest też \(\displaystyle{ o(x^2)}\), jednak \(\displaystyle{ o(x^3), o(x^4), \ldots}\) już nie); \(\displaystyle{ \sin x = \mathcal{O} (x)}\) jak i \(\displaystyle{ \sin x = x + \mathcal{O}(x^3)}\), itp. gdy \(\displaystyle{ x \to 0}\), ponieważ:
  \(\displaystyle{ \lim_{x \to 0} \frac{\sin x - x}{x} = \lim_{x \to 0} \left( \frac{\sin x}{x} - 1 \right) = 0, \; \; |\sin x| \le |x|, \; \; |\sin x - x| \le |x^3|}\)
• \(\displaystyle{ \sqrt{1 + x^2} = x + \mathcal{O} \left( \frac{1}{x} \right)}\) gdy \(\displaystyle{ x \to +\infty}\), gdyż:
  \(\displaystyle{ \left| \sqrt{1 + x^2} - x \right| = \left| \frac{1}{x + \sqrt{x^2 + 1}} \right| \le \frac{1}{2} \left| \frac{1}{x} \right|}\)
• \(\displaystyle{ \frac{f(x+h) - f(x)}{h} = f'(x) + \mathcal{O}(h)}\), gdy \(\displaystyle{ h \to 0}\), ponieważ:
  \(\displaystyle{ \left| \frac{f(x+h) - f(x)}{h} - f'(x) \right| = \left|f'(x + \theta h) - f'(x)\right| \le \left| \theta h f''(x) \right| \le C|h|}\)