Nick B. 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