[ScottBurson]

I understand that log-time algorithms have a marketing problem. I think the correct way to address that is the one I already suggested: give benchmark numbers for lookup, relative to ArrayList, for a typical collection size (or maybe for a few sample sizes -- 32, 1024, and 32768, perhaps). These will clearly show both that lookup is fast on small seqs and that it slows down logarithmically.

I would be more sympathetic to your argument that O(log n) is "practically" O(1) if you would put it in context. It's certainly true that how much the difference matters depends on the application. For someone doing real-time work (HFT, for example) it could be critical. For the average web app, it matters extremely little; the programmer productivity gains offered by functional collections far outweigh the small cost in CPU cycles. I totally agree with that argument, and have made it myself many times, but I still wouldn't say that log time is "practically" constant time for all applications.

[JeanPierre]

Agreed on the benchmarks – that's the next (and last) part on the list I'm going to do with this series.

And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?

[ScottBurson]

Ah, good -- numbers will clarify the situation considerably.

Personally my preference would be to argue that for applications that aren't terribly performance-sensitive, log time in general just isn't that bad. Even binary trees are quite usable for many purposes. (I believe the Linux kernel uses red-black trees for various things.) For a general-purpose sequence data structure that will be used in a variety of ways, a very good case can be made that it's worth accepting log-time lookup in order to get log-time insertion, subsequence, and concatenation -- operations that all take linear time on an ArrayList (and linear time will kill you far sooner than log time!).

On top of that, Hickey, following Bagwell, has done a great job at keeping the constant factors down, as (I presume) the benchmark numbers will show.

Another point I would make is that true random access into a seq is not the only way elements are retrieved. Often this is done via an iterator. I presume the Clojure seq iterator takes amortized constant time per element (it should); if so, I think it would be worth pointing that out.

All that said, I guess I could live with "practically O(1) for non-HPC applications".

Sorry I was so combative. I had not looked closely at Clojure seqs, so I do appreciate this series of posts you have written.

[plinkplonk]

you should probably try "practically O(1) for the average web app", if you want to keep that phrasing.

Better to skip the "practically O(1)" etc bits and just say O(log n).