3 ms·
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 no
by scott_s 15y ago
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.