Re: Red-black trees?

Ben Pfaff wrote:
CBFalconer <cbfalconer@xxxxxxxxx> writes:

You are misunderstanding the O notation, which doesn't get
altered by the occasional slower operation.

No, you are confusing worst-case complexity with amortized
complexity. See
for an overview.


* Worst-case complexity is the maximum complexity of any
given operation. This is O(n) for insertion into a
hash table that reorganizes itself, since in the worst
case an insertion takes roughly n steps.

* Amortized complexity is the maximum complexity of a
series of operations, divided by the number of
operations. This is O(1) for a well-designed hash table.

I suspect you have put your finger on the basic disagreement here.
That's why I am a lousy teacher - when someone misunderstands I
repeat myself in slightly different words. Thanks.

[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <>
Try the download section.