>>780
自己レス。厳密に言うと、記号に微妙な誤りがあって、N個のデータがあった時、
・C++ の delete pXxx の一回当たりの平均速度を f(N)
・Java/C# の rXxx = null; の一回当たりの平均速度を g(N)
とすると、O(1)、O(N)はなく、
f(N)〜1 // 常に
g(N)〜N // 最悪ケース
と書いたほうが良かった。

g(N)=O(N) と g(N)〜N は、意味が違っていて、前者は、N が十分大きい場合に、
実行時間が最悪でも N に比例。後者は、実行時間が N が十分大きい場合に N に比例。
言い方を帰れば、=O(N)という記号は、(Nが大きい場合の)上限値、
〜Nという記号は、Nが大きい場合の漸近値を表す。