You are, on the matter of what these notations mean, absolutely right. This "effectively constant time" claim didn't originate from Clojure, by the way. Scala,

You are, on the matter of what these notations mean, absolutely right. This "effectively constant time" claim didn't originate from Clojure, by the way. Scala, which has similar 32-tree structures, used it before then. In functional programming, binary-tree structures were common for maps and sets (and still are, in Haskell and Ocaml) because they can use comparisons without hashing and can be faster. However, those trees tend to involve ~log2 n bounces, which can become a performance problem if they're very big. People end up preferring (less functional, and less performant due to hashing if your collection is small) hash tables. The 32-tree structures are great, on the whole. Not only do they offer fast lookups, but the amount of copying that has to be done for inserts and deletions is generally very small. The "effectively constant" language emerged as a way of saying, "you're not necessarily going to want to replace this with a hashtable at 1,000,000 elements". Rich Hickey gave a talk early on about this in which he acknowledged the fact that it was still O(log n) time. As he said, constants matter. The reason people equate O(log n) lookup with "slow" is that they (mistakenly) assume that n ~ 1,000,000 will prima facie the lookup 20x slower than it "needs to be". And that's, of course, false.