Old but still relevant, and since innoq link-rots.
Jarkko Oranen a.k.a. Chousuke posted an excellent table summarizing the performance characteristics of functions operating on different Clojure data structures:
| hash-map | sorted-map | hash-set | sorted-set | vector | queue | list | lazy seq | |
|---|---|---|---|---|---|---|---|---|
| conj | near-constant | logarithmic | near-constant | logarithmic | constant (tail) | constant (tail) | constant (head) | constant (head) |
| assoc | near-constant | logarithmic | - | - | near-constant | - | - | - |
| dissoc | near-constant | logarithmic | - | - | - | - | - | - |
| disj | - | - | near-constant | logarithmic | - | - | - | - |
| nth | - | - | - | - | near-constant | linear | linear | linear |
| get | near-constant | logarithmic | near-constant | logarithmic | near-constant | - | - | - |
| pop | - | - | - | - | constant (tail) | constant (head) | constant (head) | constant (head) |
| peek | - | - | - | - | constant (tail) | constant (head) | constant (head) | constant (head) |
| count | constant | constant | constant | constant | constant | constant | constant | linear |
- constant means O(1) complexity, in other words, the time required for the operation is constant and independent of the number of elements contained in the collection. If you think of s simple linked list, you can imagine that adding something to its front always involves the same number of steps, regardless of the number of elements. This is the fastest you can hope for.
- linear is the slowest that can happen (in the Clojure libs, that is): This is O(n) complexity, meaning that the time required for applying this function on a list with 1000 elements will take a 100 times as long as applying it to a list of 10. In other words: this is slow.
- logarithmic means that the time required requires log n hops, which is pretty fast (e.g. doing this operation on a list of 1,000,000 items takes 6 times as long as doing it on a list with 10)
- near-constant performance characteristics refer to the places where the underlying tree structure for most (all?) of Clojure's collections shows its benefits: The number of hops required (as Rich puts it) is log32 n. (Update: I've erased the naïve explanation I had here, will follow up with a better one soon.)
Some operations are, of course not supported on some structures.