You're right that it's supposed to be the absolute upper bound. From a purely mathematical perspective, I agree completely. I wish I could edit my post to say:

>By definition, a O(log n) structure takes, for most inputs, no more than log n operations to get to the node you want to get to.

However, from a CS perspective, I still think that it's important to stress that the inputs do matter.

Big-O is not intended to be a worst-case analysis on running time. There are a lot of assumptions that go into the analysis on the inputs.

For example, it's generally accepted that binary search tree lookup is O(log n). However, if you have a very badly unbalanced tree, the lookup time could be O(n).

Sorry, but that's exactly what Big-O analysis is intended to do. If you have an binary search tree that can be imbalanced, then the lookup time is O(n). It's not "can be," it is. Worst-case analysis is across all inputs. Not "for most," but all.

The only binary search trees that people use in practice are balanced. That is, the algorithms that control insertion and deletion in the tree guarantee that the tree is always balanced, and they themselves run in O(log n) time. In my experience, most trees used in practice are in fact red-black trees, but a much easier to understand balanced binary tree is an AVL tree. So when we say that a red-black tree has O(log n) lookup, that is a guarantee across all inputs. There is no input to a red-black tree that will yield a linear lookup time.