ランダウの記号
より複雑な使い方としては、O( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるというものがある。例えば、以下は n → ∞ で正しい内容を記述している。
( n + 1 ) 2 = n 2 + O ( n ) , ( n + O ( n 1 / 2 ) ) ( n + O ( log n ) ) 2 = n 3 + O ( n 5 / 2 ) , n O ( 1 ) = O ( e n ) . {\displaystyle {\begin{aligned}&(n+1)^{2}=n^{2}+O(n),\\&(n+O(n^{1/2}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2}),\\&n^{O(1)}=O(e^{n}).\end{aligned}}}
これらの式の意味は、次のように解釈する:
左辺の O() を満たす「任意の」関数に対して、右辺の O() を満たす「ある」関数を適切に選べば、それらの関数を代入した等式の両辺が等しいようにできる。
例えば三つの目の式は、
であるから、C = 13, x0 = 1 とおけばよい。
リーマン予想が正しければ、x 以下の素数の個数 π(x) は次のように π ( x ) = ∫ 2 x d t log  t + O ( x log  x ) {\displaystyle \pi (x)=\int _{2}^{x}{\frac {dt}{\log t}}+O({\sqrt {x}}\,\log x)} と評価できる(素数定理も参照)。
バブルソートの時間的計算量を考えると、n 個の要素からなる列をソートするのに掛かる時間はO(n) である。クイックソートを使えば、平均計算時間を O(n log n) に改善できる(但し最悪時にはO(n))。
n 次正方行列の固有値を求めるアルゴリズムは、少なくともその行列に含まれる n 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は Ω(n) である。
すなわち、一般的な行列に対してその固有値を計算するのに掛かる時間が n のオーダーを下回るアルゴリズムは存在しない。
漸近記法は多変数になっても有効である。たとえば
f ( n , m ) = n 2 + m 3 + O ( n + m ) ( as n , m → ∞ ) {\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad ({\mbox{as }}n,m\to \infty )}
という言及が示唆するのは、定数 C, N で
∀ n , m > N : | g ( n , m ) | ≤ C ( n + m ) {\displaystyle \forall n,m>N:|g(n,m)|\leq C(n+m)}
を満たすものの存在である。ここで g(n, m) は
f ( n , m ) = n 2 + m 3 + g ( n , m ) {\displaystyle f(n,m)=n^{2}+m^{3}+g(n,m)}
で定められるものである。混乱を避けるためには、動かす変数は常に明示する必要がある。つまり
f ( n , m ) = O ( n m ) ( as n , m → ∞ ) {\displaystyle f(n,m)=O(n^{m})\quad ({\mbox{as }}n,m\to \infty )}
という言明は、次の
∀ m : f ( n , m ) = O ( n m ) ( as n → ∞ ) {\displaystyle \forall m:f(n,m)=O(n^{m})\quad ({\mbox{as }}n\to \infty )}
とは明確に異なる言明である。
O ( O ( f ( n ) ) ) = O ( f ( n ) ) . {\displaystyle O(O(f(n)))=O(f(n)).}
また p(n) と q(n) をゼロでない n の多項式とすると
p ( n ) = O ( q ( n ) ) ⟺ deg  p ( n ) ≤ deg  q ( n ) p ( n ) = o ( q ( n ) ) ⟺ deg  p ( n ) < deg  q ( n ) {\displaystyle {\begin{aligned}&p(n)=O(q(n))&&\iff &&\deg p(n)\leq \deg q(n)\\&p(n)=o(q(n))&&\iff &&\deg p(n)<\deg q(n)\end{aligned}}}
が成り立つ。