O記法は計算にかかる時間とデータ量の関係について便利な記法

$$O(n)$$
「$n$ のオーダーである」，「オーダーエヌ」，「オーエヌ」，「線形時間」と呼ぶ．
配列への挿入のように「データの量 $n$ が2倍になったら計算時間も2倍くらいになる」という性質

$$O(1)$$
「定数のオーダーである」，「オーダーイチ」，「オーワン」，「定数時間」と呼ぶ．
連結リストへの挿入のように「データの量 $n$ が2倍になろうが計算時間は変わらない」という性質

$$O(n^{2})$$
データ量 $n$ が2倍，3倍になったときに，計算時間が4倍，9倍に増える

$$O(\log n)$$
データ量 $n$ が2倍になったときに増える計算時間と，データ量が2倍から4倍になった時に増える計算時間が同じくらい

O記法は関数の増え方をざっくりと表現するものなので，$n^{2}+2n+1$ であっても $3n^{2}$ であっても，どちらも $O(n^{2})$

厳密な定義の解説はたとえば，奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年．を参照して欲しい