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.

Actually the best- and (ensemble) average-case complexities of his insertion
function may also be O(n) the same as the worst case because the resizes
occur at the same sizes regardless of the transaction history.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
.



Relevant Pages

  • Re: David Dryden - Searching All of Sequence Space
    ... informational complexity, which looks more and more like a failed ... phenomenon or functionality. ... confusing different definitions of the term "complexity". ... you're confusing the product with the process. ...
    (talk.origins)
  • Re: Red-black trees?
    ... you are confusing worst-case complexity with amortized ... Actually the best- and (ensemble) average-case complexities of ...
    (comp.programming)
  • Re: David Dryden - Searching All of Sequence Space
    ... informational complexity, which looks more and more like a failed ... phenomenon or functionality. ... confusing different definitions of the term "complexity". ... you're confusing the product with the process. ...
    (talk.origins)
  • Re: Snowflake Complexity?
    ... complexity - not random complexity or algorithmic complexity. ... a book contains more Shannon information than a book of equal size ... this description is very confusing since it seems ...
    (talk.origins)
  • Re: David Dryden - Searching All of Sequence Space
    ... confusing different definitions of the term "complexity". ... The granite cube is the product. ... you're confusing the product with the process. ... by using hair brushes on stone or as th eoffal of a species with a ...
    (talk.origins)