Efficiency
In earlier chapters, when we analyzed the performance of OrderedSet operations implemented as a Binary Search Tree, we established:
Each of the operations start at the root and follow path down to potentially the leaf at the deepest level. The time complexity of the operations is, therefore, $O(h)$ where $h$ is the height of the tree.
In the worst case, all the nodes in the BST will be arranged in a single path. Therefore, the core operations take $O(n)$ time on a collection of $n$ elements.
In the best case, the BST is a full binary tree with the height of $O(\lg n)$. Therefore, the core operations take $O(\lg n)$ time on a collection of $n$ elements.