>>779
O(x)という記号の意味を大体書いておくと、
O(1) = データ量Nが大きくなっても処理時間に変化が起きない。
O(N) = データ量Nが大きくなると、処理時間がNに比例して大きくなっていく。

もう少し厳密に書くと、delete pXxx や rXxx = null にかかる処理時間を f(N) と表した時、

O(1) : lim_{N->∞) ( f(N) ) < 一定値
O(N) : lim_{N->∞) ( f(N) / N ) < 一定値

ということです。これらは数学の解析学や微分積分学のランダウの記号といいます。