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.
Here is a table composed by John Jacobsen and taken from this discussion:
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
):
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With