>>175
[補足]
このことは、
f(N) = O(g(N))
とも書く。以下、厳密性はないが、理解のために書いておけば、
f(N)=O(1)とは、大まかに言って f(N) = b
f(N)=O(N)とは、大まかに言って f(N) = a・N + b
f(N)=O(N^2)とは、大まかに言って f(N) = a2・N^2 + a1・N + b
を意味する。だから、
f'(N)=O(N/2)とは、大まかに言って f'(N) = a・N/2 + b のような意味になるから、
a' = a / 2 と書いてしまえば、
f'(N) = a'・N + b となり、f'(N)=O(N)と言えることが分かる。
f''(N)=O(N)+O(1) は、大まかに言って、
f''(N)= { a・N + b1 } + b2 = a・N + (b1+b2) であるから、
f''(N)=O(N) であることがわかる。従って、

O(N/2)+O(1)=O(N)
であることが分かる。