o 記法・ω 記法

定義 3.2（「計算量と O 記法」§3）

\begin{aligned} o(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \le c\,g(n) \,\} \\ \omega(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \ge c\,g(n) \,\} \end{aligned}

$f \in o(g)$ のとき「 $f$ は $g$ より真に小さいオーダーである」と読む。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。