small-o記法
small-o notation
ある関数が他の関数より漸近的に小さいことを示す
例
$ \sqrt{n}=o(n)
$ n^2=o(n^3)
定義
$ f,g:\mathbb{N}\rightarrow\mathbb{R}^+に対して、$ \lim_{n\rightarrow\infin}\frac{f(n)}{g(n)}=0ならば、$ f(n)=o(g(n))という。
換言すると、$ f(n)=o(g(n))は、任意の実数$ c\gt0に対して、数$ n_0が存在し、全ての$ n\ge n_0に対して、$ f(n)\lt c g(n)