Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 706
Anonymous Avatar asked Jun 11 '13 15:06

Anonymous


2 Answers

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

enter image description here

like image 145
om-nom-nom Avatar answered Oct 21 '22 10:10

om-nom-nom


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.

like image 26
brymck Avatar answered Oct 21 '22 11:10

brymck