O 記法・Ω 記法・Θ 記法

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

関数 $g$ に対し、関数の集合 $O(g)$ , $\Omega(g)$ , $\Theta(g)$ を次で定める。

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

$f \in O(g)$ を慣用的に $f(n) = O(g(n))$ とも書き、「 $f$ は高々 $g$ のオーダーである」と読む。

閉包の状態

定義

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

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