# Re: Red-black trees?

*From*: CBFalconer <cbfalconer@xxxxxxxxx>*Date*: Wed, 19 Nov 2008 00:36:46 -0500

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 http://en.wikipedia.org/wiki/Amortized_analysis

for an overview.

Basically:

* 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]: <http://cbfalconer.home.att.net>

Try the download section.

.

**References**:**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Ben Pfaff

- Prev by Date:
**Re: Red-black trees?** - Next by Date:
**Re: fast stable sort** - Previous by thread:
**Re: Red-black trees?** - Next by thread:
**Re: Red-black trees?** - Index(es):