Re: Redblack trees?
 From: Ben Pfaff <blp@xxxxxxxxxxxxxxx>
 Date: Tue, 18 Nov 2008 21:19:12 0800
CBFalconer <cbfalconer@xxxxxxxxx> writes:
You are misunderstanding the O notation, which doesn't get
altered by the occasional slower operation.
No, you are confusing worstcase complexity with amortized
complexity. See http://en.wikipedia.org/wiki/Amortized_analysis
for an overview.
Basically:
* Worstcase 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 welldesigned hash
table.

"A computer is a state machine.
Threads are for people who cant [sic] program state machines."
Alan Cox
.
 FollowUps:
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 References:
 Re: Redblack trees?
 From: Mark Wooding
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: Mark Wooding
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: Mark Wooding
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 From: Jon Harrop
 Re: Redblack trees?
 From: CBFalconer
 Re: Redblack trees?
 Prev by Date: What is Complexity?
 Next by Date: Re: Redblack trees?
 Previous by thread: Re: Redblack trees?
 Next by thread: Re: Redblack trees?
 Index(es):
Relevant Pages
