周りの人が O 記法を正しく使えていない気がしてもやもやしたので，えびちゃんの理解を書きます．
「数学ガール 乱択アルゴリズム」の pp. 193–204 に書かれていることが正しいと思っているので，手軽に読める環境にある人は読んでほしいです． www.amazon.co.jp
定義
そもそも，O 記法は計算量に限って使われる記法ではなく，関数の漸近的な挙動を記述するためのものだと思っています． この文脈でのオーダーとは order of growth のことであって，（関数の）増加の度合いのことを指します．
ある関数 \(f(n)\) と \(g(n)\) に対して，以下を満たすとき \(f(n) = O(g(n))\) とか \(f(n) \in O(g(n))\) と書きます． \[ \exists n_0 \in \mathbb{N}, \exists k > 0, \forall n \ge n_0: |f(n)| \le k\cdot g(n) \] 要するに，十分に大きい \(n\) では \(f(n)\) の絶対値は \(g(n)\) の定数倍で上から抑えられるという主張です．
このとき，「\(f(n)\) は たかだか \(g(n)\) のオーダーである」と言います．
読み方
たとえば，定義から明らかに \(n \in O(n^2)\) ですね． オーダーとは増加の度合いのことでしたので，これを（「たかだか」を除いて）「\(n\) は \(n^2\) のオーダーである」などと読むのは気持ち悪く感じます*1．
「\(f(n) \in O(g(n))\)」を読むときも「\(f(n)\) はオーダー \(g(n)\) である」とか読まずに「\(f(n)\) は（ビッグ）オーの \(g(n)\) である」とか読んだ方が自然だと思っています．
「\(2n+1\) は \(n\) のオーダーである」も「\(2n+1\in O(n)\)」も正しい文ですが，前者の文は後者の文に対応する読み方ではないのでは？ という気持ちがあります．
単に「これこれのオーダーである」と言われると「ちょうどそのオーダーである」と言われているように感じませんか？ そう言いたいときは \(\Theta\) 記法を使う方が適切だと思います．
計算量との関わり
あるアルゴリズムの実行にかかるステップ数を考えます．
入力の大きさ*2が \(n\) のときにステップ数が \(T(n)\) と表せたとします． 何を 1 ステップと見るかは状況によりそうですが，競プロなどの文脈では加算や大小比較など 1 回を 1 ステップでできると見なしていると思います．
その \(T(n)\) が，たかだかある関数 \(f(n)\) のオーダーであるとき，そのアルゴリズムの（時間）計算量は \(O(f(n))\) であると言われます． ステップ数 \(T(n)\) が最悪時のものを元に計算されたのであれば最悪（時間）計算量と言われます．cf. 最良計算量，平均計算量．
実際には「加算が何回で比較が何回で...」などと数えてステップ数を数えるのは面倒ですから，for のネストの数などを数えて \(O(f(n))\) だけを与えることが多いですね．
\(O(f(n))\) という表記だけでは，ある大きさ \(n\) の入力が与えられたときのステップ数自体には触れていないことに注意してください．
たとえば，内側のループで 0 から n まで回すときと 0 から i まで回すときではオーダーは同じですがステップ数は異なりますね．
怪しい記法
\(O(10^9)\) とか \(O(n^2/64)\) のような記法を見たことがありますか？ おもしろいですね．
たとえば，\(O(n^3)\) のアルゴリズムがあって，想定される \(n\) の最大値が \(10^3\) のようなとき，「計算量は \(O(10^9)\) です」とか言う人がいます． また，ある \(O(n^2)\) のアルゴリズムを \(64\) 倍高速化したとき，「計算量は \(O(n^2/64)\) です」とか言う人がいます．
\(O(10^9)\) という表記が意味するところは \(O(1)\) と同じなんですよね． 計算量の話をするとき，必ずしも \(O\) を使う必要はないはずなんですが，無理やり \(O\) を使おうとして変にしている気がします．
もし実行ステップ数を正確に見積もれていれば「\(n \le 10^3\) なら最大実行ステップ数は \(10^9\) です」とか言ってもよさそう？
コンパイラの最適化などの関係で，必ずしもソースから考えられる実行ステップ数になるとは限らないのがひとつの難点っぽそう． さらに，除算とビット演算などでは 1 回あたりにかかる時間が大きく異なるのでステップ数だけ求めても意味がなさそう． クロック数とかで議論するべき？ そこにキャッシュがどうこうとかも効いてきて頭こわれる．
こんな感じの事情があって，細かいステップ数ではなく漸近的な挙動で議論されることが多そう？
文中での用法
「\(O(n)\) 回」のような用法もありますね（これは問題ない使い方だと思っています*3）．
以下は C++/STL の仕様での計算量規定に関する文ですが，正しく訳すことができますか？
ひとつめ：
Complexity: \(O(N)\) applications of
binary_op
ふたつめ：
Complexity: \(O(N \log N)\) comparisons
それぞれ binary_op を \(O(N)\) 回適用することと，\(O(N \log N)\) 回比較することを指していますね
*4．
O 記法をアルゴリズムの計算量を示すだけのものとして認識しているとちゃんと解釈できない気がします．
その他の用法
多項式のオーダーで抑えられるものを \(n^{O(1)}\) と書いたり，\(n\) に定数項がついたものを \(n+O(1)\) と書いたりしますね．
おわり
にゃあ
