Comment by ddtaylor

I think the notation is supposed to mean the worst performance. This is more an argument about amortized time analysis.