Ω記法 — Termwire

アルゴリズムの処理時間について、最も速い場合でもこれくらいはかかるという下限を表す記法。

O記法が最悪の場合の上限を表すのに対し、Ω記法は逆に、どんなに条件が良くてもこれ以上速くはならないという下限の目安を表す。アルゴリズムの性能を評価する際の、もうひとつの視点を提供する。

ある問題を解くのに理論上どれだけの計算が最低限必要かを議論する際、このΩ記法を使った下限の考え方が使われる。