At the beginning of part 1, the author says that this data structure provides "
practically O(1) runtime" (emphasis added) for the important operations of lookups, insertion, updating, etc. At the end it is explained how it's "O(log32 n)", which of course is actually O(log n).
And then here in part 3 where he keeps saying "effectively constant time* (emphasis in original this time), what he means is O(log n) time.
The Clojure people really need to stop doing this. Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large. It is precisely not intended to communicate the absolute time the operation takes in small cases. They are confusing people when they try to communicate both pieces of information at the same time. What they should say is something like "lookup takes O(log n) time, and for seqs of size up to N items, it takes M times as long as ArrayList.get".
And then, of course, to describe O(log n) time as "effectively constant" is just lying.
(Second and fourth paragraphs added in edit.)
And then here in part 3 where he keeps saying "effectively constant time* (emphasis in original this time), what he means is O(log n) time.
The Clojure people really need to stop doing this. Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large. It is precisely not intended to communicate the absolute time the operation takes in small cases. They are confusing people when they try to communicate both pieces of information at the same time. What they should say is something like "lookup takes O(log n) time, and for seqs of size up to N items, it takes M times as long as ArrayList.get".
And then, of course, to describe O(log n) time as "effectively constant" is just lying.
(Second and fourth paragraphs added in edit.)