ランダウの記号
十分大きい全ての実数 x に対し定義されている実数値関数 f(x) と g(x) に対し、
f ( x ) = O ( g ( x ) ) ( x → ∞ ) {\displaystyle f(x)=O(g(x))\quad (x\to \infty )}
を
∃ x 0 , ∃ M > 0 s.t. ∀ x [ x > x 0 ⇒ | f ( x ) | ≤ M | g ( x ) | ] {\displaystyle {}^{\exists }x_{0},{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[x>x_{0}\Rightarrow |f(x)|\leq M|g(x)|]}
と定義し、「f(x) が x → ∞ のとき オーダーO(g(x)) である」と呼ぶ。
また、a を実数とするとき、aの近傍で定義された実数値関数f(x) と g(x) に対し、
f ( x ) = O ( g ( x ) ) ( x → a ) {\displaystyle f(x)=O(g(x))\quad (x\to a)}
を
∃ δ > 0 , ∃ M > 0 s.
O-記法はドイツの数論家であるポール・バッハマンによって1894年に彼の著書『解析数論』(Analytische Zahlentheorie) の第二巻で初めて導入された(1892年に著された第一巻では用いられていない)。これに触発されてエドムント・ランダウが1909年にo-記法を発明した。
なお、ハーディとリトルウッドもランダウの記号 f = O ( g ) {\displaystyle f=O(g)\,} に相当するものを別の記号 f ⪯ g {\displaystyle f\preceq g\,} で表現している。彼らはΩ-記法も現在と近い意味で用いており、今日の言葉でいえば、彼らのΩはo(g)でない事を表している。
またヴィノグラードフ(英語版)は f = O ( g ) {\displaystyle f=O(g)} と f ≪ g {\displaystyle f\ll g} を同じ意味で用いている。
ドナルド・クヌースは、計算機科学の世界にO-記法を導入し、Ω-記法やΘ-記法も再導入した。