Re: Red-black trees?

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.
--
"A computer is a state machine.
Threads are for people who cant [sic] program state machines."
--Alan Cox
.

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 ... Worst-case complexity is the maximum complexity of any ... case an insertion takes roughly n steps. ... This is Ofor a well-designed hash table. ...
    (comp.programming)
  • Re: Implementation of State-Machine
    ... > complexity that makes Harel tempting. ... the root superclass does not have any knowledge ... Are you perhaps implying a particular state machine ...
    (comp.object)
  • Re: Program complexity
    ... the complexity of a Java program by analysing every line of it code. ... two state machines and then write functions that traverse the tree to ... The first state machine will be your tokenizer. ... you give it the input file from which it will read tokens ...
    (comp.unix.programmer)