Welcome! Please see the About page for a little more info on how this works.

+1 vote
in Docs by

Hi, I'm new to clojure.

I have seen that there are some big O on the data structures part. But, is there a place on documentation showing all the big O of the operations in clojure?


1 Answer

+3 votes

There are a couple of tables (from books as well) floating around that summarize core operations relative to the datastructures they are working on. Unfortunately, I don't think we support markdown here, at least not tables (I tried to paste in but no good).

This one by brymck from John Jacobsen's original table (likely derived from elsewhere).

That's a pretty good summary. If I were to make a table, I'd probably focus on a handful of expectation buckets expectation which is more general - constant, sublinear, or linear.

The other thing to know is that there are some important interfaces (exposed by predicate functions) that hint to performance classes as well. For example, Counted (check with `counted?`) says whether it can be counted in constant time and that divides the two behaviors you see on that line. Similarly, Indexed and `indexed?` and nth.

And then an important takeaway is that if a data structure can't implement an operation within the expectation constraint, we don't implement it. nth and count are kind of special exceptions as they are polymorphic across those classes above.