ランダウの記号
任意の関数 f(n) = O(1) に対し、g(n) = O(e) を満たすgを適切に選べば n f ( n ) ≤ g ( n ) {\displaystyle n^{f(n)}\leq g(n)} が成立する
事を意味する。
二つの目の式のように左辺に複数のO()がある場合は、それらすべてに対して上述のルールを適応する。したがって二つの目の式は、
任意の関数 f 1 ( n ) = O ( n 1 / 2 ) {\displaystyle f_{1}(n)=O(n^{1/2})\,} 、 f 2 ( n ) = O ( O ( log n ) ) {\displaystyle f_{2}(n)=O(O(\log \,n))\,} に対し、 g ( n ) = O ( n 5 / 2 ) {\displaystyle g(n)=O(n^{5/2})\,} を満たすgを適切に選べば ( n + f 1 ( n ) ) ( n + f 2 ( n ) ) 2 ≤ n 3 + g ( n ) {\displaystyle (n+f_{1}(n))(n+f_{2}(n))^{2}\leq n^{3}+g(n)} が成立する
事を意味する。
O-記法は次の性質を満たす。o-記法も同様の性質を満たす。
lim x → ∞ | f ( x ) g ( x ) | = 0 {\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|=0}
を表す。(厳密にはε-δ論法で定義する。)特に f(x) = o(1) は lim f(x) = 0 と同値である。
ランダウ記法は様々な分野で有益であり、たとえば指数関数を3次までテイラー展開したものは
e x = 1 + x + x 2 2 ! + x 3 3 ! + O ( x 4 ) ( x → 0 ) {\displaystyle \mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+O(x^{4})\quad (x\to 0)}
と書き表せる。
記号 O とo は通常、関数の収束や発散の漸近的な上界を記述する為に用いられる。同様に漸近的な下界を記述する為にΩ, ωという類似記法が用いられ、上下両方を記述する為にΘ という記法を用いる。
ただし、Ω、ω、Θは主に計算機科学で用いられる記法であり、数学では O と o をこれらの意味に流用する事が多い(どの意味で用いているのかは文脈から判断)。