Big-O表記
big-O notation, Landau symbol
$ f,g : \mathbb{N} \to \mathbb{N}とする
定義
$ f = O(g) \iff \exists_{c, n_0} \forall_{n > n_0} [f(n) \le c\cdot g(n)]
$ f = \Omega(g) \iff g = O(f)
$ f =_{\Theta} g \iff f = O(g) \land g = O(f)
$ f = o(g) \iff \forall_{\epsilon > 0} \exists_{n_0} \forall_{n > n_0} [f(n) \le \epsilon \cdot g(n)]
$ f = \omega(g) \iff g = o(f)
$ =のこのような用法は記号の乱用であって、正しくは$ f \in O(g)のように書くべきだと思うが、慣例的に上の表記を用いる