big O の誤用：定数と前提が次数より結果を決めることが多い

二つの実装を big O で比べられるのは、同じ入力規模の範囲内だけです。その範囲を外れると、定数・メモリ局所性・分岐予測の影響が次数を上回ります。

小さい n では低次の方が速い

挿入整列は O(n²)、クイックソートは O(n log n)。しかし n = 10 では通常、挿入整列が勝ちます。再帰も分割の手間もなく、配列を順に読むだけだからです。

標準ライブラリはまさにそうしています。小さな範囲では挿入整列に切り替え、大きな範囲でだけクイックソートを使います。

n = 10     挿入整列が 2 倍速い
n = 1000   クイックソートが 20 倍速い

したがって「O(n²) は常に使えない」は誤りです。まず n の実際の上限を確認します。

O(1) は速いという意味ではない

ハッシュ探索は償却 O(1)、配列の線形走査は O(n)。n = 8 なら配列が勝つことが多いです。キャッシュ行一回の読み出しと、ハッシュ計算に探査を比べれば明らかです。

極端な例は連結リストです。理論上は挿入 O(1) でも、たどる際に毎回ポインタを追うため、配列より一桁遅くなります。big O はメモリ配置を一切語りません。

本当の要点は前提条件

ハッシュ表の O(1) はハッシュが一様であることが前提です。攻撃者は衝突する鍵を作れ、探索は O(n) に退化します。これは理論ではなく、サービス拒否攻撃のよくある入口です。

構造	主張	前提
ハッシュ表	O(1)	一様で予測不能なハッシュ
クイックソート	O(n log n)	平均の場合、良い枢軸
動的配列への追加	償却 O(1)	倍々の拡張
B 木の探索	O(log n)	極端な偏りのない鍵分布

実際の比べ方

1. まず計測する。 プロファイル無しの最適化は当て推量です。
2. 実際の入力規模を使う。 十件と十万件では結論が逆になり得ます。
3. 定数を見る。 同じ次数の二実装が 5 倍違うのは普通です。
4. メモリを見る。 キャッシュミスは数回の追加演算より高くつきます。

big O が答えるのは「データが倍になったときどれだけ遅くなるか」です。「どちらが速いか」ではありません。問いを混ぜないことです。