> of those composite data types (which also includes assoc-lists and...?), it is the only one with O(logn) for any of its functions (particularly search).

I think you meant "all", not "any", since assoc list offers O(lg n) performance for one of its functions. In any case, this is incorrect. You can build any tree-like data structure you like with cons and nil, and, as pointed out elsewhere, Okasaki (as well as others before him), have demonstrated several tree-like data structures with O(lg n) cons, car, cdr, and nth equivalents.

Which function on assoc lists is O(log n)?

> Which function on assoc lists is O(log n)?

acons is O(1), and the O() notation is for upper bounds, so anything O(1) is also O(lg n).

Strictly speaking, no. Precisely because O-notation defines the worst case. O(1) is not O(log n), since the list insert will never exhibit log behavior.

Strictly speaking, yes. O-notation describes the growth of a function as the argument tends to infinity. Formally, the statement "f(x) is O(g(x))" means that there's some point x_0 such that f(x) is less than a constant factor times g(x) for any x > x_0.

This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)).

An algorithm can be O of different g(x)s, depending on the properties of the input. For example, the runtime of a naive quicksort implementation (which always chooses the leftmost value as a pivot) is O(n^2) if the input list is sorted, while it has runtime O(n*lg(n)) on average and in the best case (where the pivot is always the median of the section of the list being partitioned).

> This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)).

It is not, because constant function has no logarithmic behavior. To distinguish that is the whole point of big-O notation. When you tell someone "this is a O(logn) operation" they do expect log performance.

Yes O(c) is strictly under O(n) too, but so what? We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.

> It would be one of those formally correct but practically useless definitions.

"Hi, my name is Aperiodic, and I'm... a mathematician."

"Hi Aperiodic."

"It all started out so easily; you know, a few lemmas with the boys in the evenings. But before I knew it, I was picking up Bourbaki as soon as I got home from work. I would wake up in the mornings, surrounded loose sheets of paper covered in commutative diagrams, without a clear idea of what I did last night..."

> When you tell someone "this is a O(logn) operation" they do expect log performance.

If you look in the appendix of your algorithms textbook that explains big-O notation, you will see this is not the actual definition. I'm sorry if my usage confused you, but I was using it in the formal sense of "there exists an N such that there exists a c such that for all m > N, f(m) <= c*g(m)". In your log example, we can choose N = 2 and c = 1.

> We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.

For saying "f is doubly-exponential", use Theta. For saying "f is doubly-exponential or smaller", use big-O.

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma...