計算量解析の落とし穴？ f(x) ≤ g(x) + O(1) が意味する真実とは

アルゴリズムの解析でよく見かける不等式「f(x) ≤ g(x) + O(1)」。これ、正確にはどういう意味か理解していますか？単なる定数項の無視に見えて、実は漸近的挙動（Asymptotics）を扱う上で重要なニュアンスを含んでいます。この不等式が示す限界と、計算量の評価において「定数項以下の誤差」をどう捉えるべきかについて深掘りします。

コンピュータサイエンスの学生は標準的な f(x)=O(g(x)) 記法に慣れているべきだ

f(x) ∈ O(g(x)) じゃなくてあんな風に書くのは、ずっとすごく紛らわしいと思ってたんだよね。要素を表すために総和の算術記法を適用したいって気持ちはわかるけど、等式じゃないのに等号（=）でこの記法を「結んじゃう」のは…混乱の元になるよね。

混乱が起きるのは、厳密に言えば $f(x) = O(g(x))$ が記法の乱用だからだと思う。$O(g(n))$ や $\Theta(g(n))$ とその仲間たちは「集合」なんだよね。関数が集合と等しいなんて言えないし、関数が別の関数より「小さい」とも言えない。でも、数学ってのは悪名高いことに JavaScript で動いてるようなもんだから、型エラーを出す代わりに何とかして動かそうとしちゃうんだ。

ここで言う「小さい」は「最終的にすべての値で小さくなる」って解釈されるし、「集合を足す」は「その集合の任意の関数を足す」って解釈される。

漸近記法としてのこの書き方はずっと好きになれなかったし、いつも $f(x) \in O(g(x))$ スタイルの方がいいなと思ってたけど、まあ結局のところはただの記法なんだけどね。