>>151
要素数Nの時に何らかの処理Aに掛かる時間をf(N)とするとき、
O(g(N))は、ある N0 があって、N0 より大きな どんな実数 N に対しても、
f(N) / g(N) < アルファ
が成り立つことを意味し、「押さえられる無限大」、といい、
ランダウ記号(の一種)、または、ラージO 記法という。

だから、O(N/2)=O(N)であり、O(N)+O(1)=O(N)である。