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 O(h)\Omicron(h), where hh 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)\Omicron(n) time on a collection of nn elements.

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