CODEWITHSUNDEEP
clojurebig-oasymptotic-complexity
Anonymous
Anonymous

Reputation: 769

Big O of clojure library functions

Can anyone point me to a resource that lists the Big-O complexity of basic clojure library functions such as conj, cons, etc.? I know that Big-O would vary depending on the type of the input, but still, is such a resource available? I feel uncomfortable coding something without having a rough idea of how quickly it'll run.

Upvotes: 10

Views: 3723

Answers (2)

brymck
brymck

Reputation: 7663

Late to the party here, but I found the link in the comments of the first answer to be more definitive, so I'm reposting it here with a few modifications (that is, english->big-o):

enter image description here
Table Markdown source

On unsorted collections, O(log32n) is nearly constant time, and because 232 nodes can fit in the bit-partitioned trie nodes, this means a worst-case complexity of log32232 = 6.4. Vectors are also tries where the indices are keys.

Sorted collections utilize binary search where possible. (Yes, these are both technically O(log n); including the constant factor is for reference.)

Lists guarantee constant time for operations on the first element and O(n) for everything else.

Upvotes: 13

om-nom-nom
om-nom-nom

Reputation: 62835

Here is a table composed by John Jacobsen and taken from this discussion:

enter image description here

Upvotes: 22

Related Questions