Efficiency
In earlier chapters, when we analyzed the performance of OrderedSet operations implemented as a Binary Search Tree, we established:
Each of the operations starts at the root and follows a path down to potentially the leaf at the deepest level. Therefore, the time complexity of each operation is $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.