Question

BST sort N items (vanilla BST). This has a worst-case time complexity of...

a. O(1)
b. O(log N)
c. O(N)
d. O(N²)

Answer 1

The worst-case time complexity of sorting N items with a vanilla Binary Search Tree (BST) is O(N²), particularly when the tree is skewed and resembles a linked list.

Step-by-step explanation:

When sorting N items using a vanilla Binary Search Tree (BST), the worst-case time complexity is O(N²). This worst-case scenario occurs when the items are inserted into the BST in such a manner that the tree becomes skewed, effectively resembling a linked list. For instance, inserting items that are already sorted in ascending or descending order would result in this skewed structure. Consequently, each insertion takes O(N) time since it needs to traverse the tree from the root to the leaf for every insertion, and this adds up to O(N²) for N insertions.