ランダウの記号
上で定義された
f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))}
という記法は広く用いられている確立した慣習ではあるが紛らわしい記法の濫用で、二つの関数が等しいという意味ではない。
この記法の濫用は、等号の両辺にO -記法が登場した際に問題となり、例えばx →∞のとき、
O ( x ) = O ( x 2 ) {\displaystyle O(x)=O(x^{2})} であるが、 O ( x 2 ) ≠ O ( x ) {\displaystyle O(x^{2})\neq O(x)} である。
すなわち、両辺にO -記法が登場した場合には、直観的には十分大きなx で左辺/右辺が定数未満になる事を意味する。
こうした記法上の問題を回避する為に、
f ∈ O ( g ) {\displaystyle f\in O(g)}
ないし、
f ( x ) ≤ O ( g ( x ) ) {\displaystyle f(x)\leq O(g(x))}
と書く流儀もあるが、一般的ではない。前者の場合、「O(g)」 は g の定数倍によって押さえられる関数全体からなる集合であるとみなしていることになる。
f ( n ) = O ( g ( n ) ) , g ( n ) = O ( h ( n ) ) ⟹ f ( n ) = O ( h ( n ) ) . {\displaystyle f(n)=O(g(n)),\ g(n)=O(h(n))\implies f(n)=O(h(n)).}