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 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.
.

Relevant Pages

  • Re: Remove items from list while enumerating
    ... The runtime complexity would be the same as if you just ... I meant recreating it omitting the removed items. ... insertion point you may have to spend about the same as to perform an ... then the number of resizing operations would be log-base-2. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: How to use set_union algorithm?
    ... Seriously, though, the complexity is ... specified in the standard, 23.3.5.2 para 4. ... > through the set to find the insertion place for each element even if ... But the version of the insert member function above has the ...
    (comp.lang.cpp)
  • Re: Red-black trees?
    ... you are confusing worst-case complexity with amortized ... case an insertion takes roughly n steps. ... This is Ofor a well-designed hash ... "A computer is a state machine. ...
    (comp.programming)