from 計算量

ある関数が他の関数より漸近的に小さいことを示す

例

\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)