Efficiency

  • Recall efficiency of BST operation.

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 $\Omicron(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 $\Omicron(n)$ time on a collection of $n$ elements.

In the best-case, the BST is a full binary tree with the height of $\Omicron(\lg n)$. Therefore, the core operations take $\Omicron(\lg n)$ time on a collection of $n$ elements.