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: 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)
  • 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)