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:
-
5An "1" in quotes, is that close enough to one to not matter (according to Rich Hickey.) But really is O(log_32 depth)? – Shannon Severance Jun 11 '13 at 22:15
-
This table is not entirely correct.
last
is always O(n).cons
is always O(1) (assumingseq
is always O(1)).conj
in a vector is only "1", not 1. – kotarak Jun 12 '13 at 7:54 -
@kotarak Would you be able to elaborate a little on your corrections? :) – Anonymous Jun 12 '13 at 14:17
-
@Anonymous
last
creates a sequence and walks it. Hence, O(n).cons
just creates a Cons object and callsseq
on its second arg. So as long asseq
is O(1),cons
is O(1).conj
on a vector is "usually" O(1), but at some point arrays have to be moved around under the hood. So worst-case is O(log32 n) aka. O("1"). – kotarak Jun 13 '13 at 5:49 -
2I'm the author of the table above and indeed it was my first stab at summarizing my imperfect knowledge at the time -- innoq.com/blog/st/2010/04/clojure_performance_guarantees.html looks to be more definitive. – JohnJ Jun 28 '13 at 1:21
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
):
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.