A few corrections:
Lists are single linked lists, so nth on them (as well as last) is O(n).
Get on lists is unsupported.
Cons on a vector is O(1) since cons converts things to seqs (O(1)) before
constructing the cons.
Count on everything but Cons and LazySeq is O(1). For those two it's O(n)
until it hits something in the list that implements Counted (normally
PersistentList), then it's O(1) from there on. You might want to list
Cons/LazySeq separate from PersistentList for this reason.
So, cons on a String. That's a interesting question. Cons on anything is
O(1). For a string it's the cost of creating a StringSeq on the Java
String, then creating a Cons cell who's next pointer references the
StringSeq. So that's O(1). But you're now left with a seq, not a string. If
you're looking for something like this (str "c" "bar") then yes, that is
O(n).
Timothy
On Wed, May 22, 2013 at 8:05 AM, John Jacobsen <eigenhom...@gmail.com>wrote:
> I'm studying for an interview and thought it might be nice to know the
> time complexity of primitive operations on collections in Clojure. A quick
> googling didn't turn up a definitive resource. I would be happy to put one
> together. What I had in mind was something like:
>
> Collections: strings, sets, maps, Java arrays, lists, vectors
> Operations: peek, pop, conj, cons, assoc/dissoc, get, nth, count
>
> What I have in mind is to fill out this table with the appropriate average
> big-O (my *guesses* from googling/experimenting/thinking are entered, and
> may be completely wrong!; sorry for any formatting problems due to varying
> type styles, perhaps I should have used s-expressions :-) - should be OK
> with fixed width font):
>
> Collection get nth cons conj assoc pop peek count
> List "1"? "1"? 1 1 X 1 1 1
> Vector "1" "1"? n 1 "1"? 1 1 1
> Set "1" X "1" "1" X X X 1?
> Map "1" X 1 "1"? "1"? X X 1?
> String 1 1 n X X X X 1
> Java Array 1 1 n X X X X 1
>
> Where O("1") is really O(log_{32}(n)), "effectively constant time" as
> opposed to "true" O(1). X obviously means you can't do the operation on
> that type. Some operations involve casting e.g. a string to a seq; I
> assume O(n) in that case (?).
>
> (It's probably obvious to everyone else, but it's cool that there are so
> few 'n's in the table.)
>
> Any corrections, operations to add, data structures to add? I imagine
> between all the readers of the list, correcting this table will be trivial.
> I am happy to post the resulting table on my blog or anywhere else.
>
> Thanks!
> John
>
> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
