ランダウの記号
アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い因数分解のアルゴリズムもこれに含まれる。
O(log n) と O(log(n)) は全く等価である。なぜならば、log(n) = c log n より2つの指数関数は定数係数のみが異なり、これは big O-記法では無視されるからである。同様に異なる底を持つ対数関数も等価であるが、一方、異なる底を持つ指数関数は等価ではない。これはよくある勘違いである。例えば、2 と 3 は同じオーダーではない。
入力サイズの単位の変更は、アルゴリズムの計算量を変えるかもしれないしそうでないかもしれない。単位を変更するということは、関数に現れる全ての n にある定数を掛けることと同じである。例えば、アルゴリズムが n のオーダーで動くとき、n を cn で置き換えれば計算量は cn となり、big O-記法では c は無視されるので計算量は変化しない (cn ∈ O(n))。しかし例えば 2 のオーダーで動くアルゴリズムでは、n を cn で置き換えると計算量は 2 = (2) となる。これは 2 とは等しくない(もちろん、c = 1 の場合を除く)。
t. ∀ x [ 0 < | x − a | < δ ⇒ | f ( x ) | ≤ M | g ( x ) | ] {\displaystyle {}^{\exists }\delta >0,{}^{\exists }M>0\quad {\text{ s.t. }}\quad {}^{\forall }x\;[0<|x-a|<\delta \Rightarrow |f(x)|\leq M|g(x)|]}
で定義し、「f(x) が x → a のとき オーダーO(g(x)) である」と呼ぶ。
なお、a の十分近くで g(x) が 0 を値にとらない場合、 f ( x ) = O ( g ( x ) ) {\displaystyle f(x)=O(g(x))} は
lim ̄ x → a  | f ( x ) g ( x ) | < ∞ {\displaystyle \varlimsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }
が満たされることと同値である(a が∞の場合も同様)。特に f(x) = O(1) は、近傍において f(x) が有界であることと同値である。
関数 f(n) が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が f(n) のオーダーを決定づける。以下にその例を挙げる。
f ( n ) = 9 log  n + 5 ( log  n ) 3 + 3 n 2 + 2 n 3 ∈ O ( n 3 ) . {\displaystyle f(n)=9\log n+5(\log n)^{3}+3n^{2}+2n^{3}\in O(n^{3}).}
例での場合、係数を無視してnに関する項を見ると、log n、(log n)、n、nの4つが存在し、このうちnが最も発散が速い。そのため、他のnに関する項に関わらず、オーダーはO(n)とする。
特に、関数が n の多項式でおさえられるならば、n が無限大に発散するに従ってより低いオーダーの項まで無視できるようになる。
O(n) と O(c) は全く異なる。前者の定数 cがどれほど大きかろうと、後者の方がずっとずっと速く発散する。どのような定数 c に対しても nより速く発散する関数は超多項式 (superpolynomial) と呼ばれる。また、どのような定数 c に対しても c よりも遅く発散する関数は準指数関数 (subexponential) と呼ばれる。