ランダウの記号
O ( f ( n ) ) + O ( f ( n ) ) = O ( f ( n ) ) . {\displaystyle O(f(n))+O(f(n))=O(f(n)).}
関数のとりうる値は、絶対値をノルムに取り替えるだけでそのまま任意のノルム線型空間の元に一般化できる。f や g は同じ空間に値を取る必要はない。g のとる値は任意の位相群の元にすることも可能である。
「極限操作」"x → x0" は、勝手なフィルター基の導入によって f と g の有向点族として一般化される。
o-記法は微分の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を
f ∼ g ⟺ ( f − g ) = o ( g ) {\displaystyle f\sim g\iff (f-g)=o(g)}
と定めることができる。これは同値関係であり、上述の f が Θ(g) 程度であるという関係よりもなお強い制限を表す記法になっている。f と g が正値実数値関数なら lim f/g = 1 なる関係式に簡略化できる。例えば、2x は Θ(x) のオーダーだが、 2x − x は o(x) のオーダーでない。
O-記法と関連がある、Ω-記法、ω-記法、Θ-記法を導入する。
Ω-記法とω-記法はそれぞれ、O-記法とo-記法の定義で大小を反転させる事により得られる。Θ-記法Θ(g)は O(g) と Ω(g) を両方満たすことを意味する。
ただし、Ω-記法に関しては、この記法を初めて導入したハーディーとリトルウッドは今日のそれとは若干異なった意味に用いていたので、あわせてそれも記す。(以下の表の「HLの定義」の部分)。
今日の定義との違いの要点をかいつまんでいえば、今日の定義ではΩ-記法は前述のようにO-記法の定義の大小反転だが、ハーディー達の定義ではΩ(g)はo(g)を満たさない事として定義していた。
両者の定義は性質のよい関数、例えば多項式に対しては同値だが、極限に近づく際に振動するような関数に関しては必ずしも同値ではない。

また、計算機科学では
f ( n ) = O ~ ( g ( n ) ) {\displaystyle f(n)={\tilde {O}}(g(n))}
を
∃ k s.t. f ( n ) = O ( g ( n ) log k  ( g ( n ) ) ) {\displaystyle \exists k\quad {\text{ s.t. }}\quad f(n)=O(g(n)\log ^{k}(g(n)))}
の意味で用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは log(n) が任意の定数 k と正の定数 ε に対して常にo(n) となるからである。
計算機科学、特に計算量理論、アルゴリズム論、暗号理論では、アルゴリズムの計算時間を評価するのに O-記法を頻繁に用いる。
アルゴリズムの計算量の評価よく使われるO-記法関数の種類を示す。
これらの中でも特に重要なものには、個別の名称がついている(多項式時間など)。
以下、 nはアルゴリズムに入力されるデータのビット数を表す。
注意しなければならないのは、アルゴリズムに整数 N を入力するときである。N のビット数 n はおよそ log2 N なので、例えば「多項式時間」といったとき、これはN の多項式ではなく n の多項式を表す。
一般的ではないが、更に発散速度の速い関数も存在する(アッカーマン関数 A(m, n) など)。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(n) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3, α ( 2 2 2 65536 − 3 ) = 4 {\displaystyle \alpha (2^{2^{2^{65536}}}-3)=4} , ...)。