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)
  • Algorithm efficiency prediciton O(n log n)
    ... Ois confusing me, how exactly do you work this out? ... table which shows for an algorithm with said complexity it takes an ... Jeffrey Spoon ...
    (comp.programming)
  • 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)