>>176
[補足2]
また厳密性を無視して大体で書くと、
f(N)=O(g(N))
の場合、f(N)のNに関する最大次数がg(N)と同じ、という意味。
だから、g(N)がNに関して k 次元だと、f(N)もNに関して k 次元、という
ことを概ね意味する。だから、大体、
f(N)=O(1) とは、f(N)=b を意味する。
f(N)=O(N) とは、f(N)=a * N + ・・・ を意味する。
f(N)=O(N^2) とは、f(N)=a * N^2 + ・・・ を意味する。
なので、f(N)=O(N/2)+O(1)だと、
f(N) = a・N/2 + b
みたいになり、これは、N に関して 1 次関数だから、Nに関する最大次数は 1。
だから、O(N)ということになる。