From: "Jörg W Mittag" <JoergWMittag+Ruby@...>
Date: 2011-02-27T07:50:27+09:00
Subject: Re: Are Hash speeds documented?

Nick Brown wrote:
> Are the lookup, insertion, deletion, and sort costs of Hash objects
> documented anywhere? I would be interested in average-case
> and worst-case times... are they linear, logarithmic, exponential, etc.
> in time?

No, as far as I know, performance characteristics are not part of the
Ruby Language Specification. Neither the Draft ISO Ruby Specification
nor RubySpec describe any kind of performance characteristics.

The popular Ruby implementations currently have the following
asymptotic time complexities and asymptotic step complexities:

    lookup:    Ο(n) worst-case, Ο(1) amortized worst-case
    insertion: Ο(n) worst-case, Ο(1) amortized worst-case
    deletion:  Ο(n) worst-case, Ο(1) amortized worst-case
    sort:      Hash doesn't have a sort method

If you want to know the average case, you need to supply a probability
distribution. Average case analysis is always relative to a
probability distribution.

But note that these are *not* part of the language specification. A
Ruby implementation can have much slower implementations and still be
a fully compliant Ruby implementation, similar to what happened with
Jscript, where array lookup was Ο(n) worst-case, Ο(n) amortized
worst-case.

jwm