ランダウの記号
O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題(例えば処理すべきデータが n 個あるなど)を解くのに掛かる時間あるいは手順数が T(n) = 4n − 2n + 2 である場合を考える。
このとき、n を次第に大きくしていくと、 T(n) に対して n の項の影響が支配的になり、他の項はほとんど無視できるようになる(たとえば n = 500 としてみると、4n の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる)。
さらに、n や 2 といった他のオーダーの式と比較する分には係数も無関係になる(たとえば T(n) = 1,000,000n のように係数が大きい関数と、それより指数が1大きい U(n) = n を比較する。仮に n = 1,000,000 としてみると T(1,000,000) = 1,000,000×1,000,000 = 1,000,000 = U(1,000,000) だから、n > 1,000,000 の場合は常に U(n) > T(n) である。)。
こうして残る影響をすくい上げて、O-記法では
T ( n ) ∈ O ( n 2 ) {\displaystyle T(n)\in O(n^{2})}
と書いて、「n のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数T(n) の増加具合が n に支配されることを表現する。