Question

Binary Search Tree (not balanced) containing N keys: ADDing a new key has AVERAGE case time complexity of...

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

Answer 1

The average case time complexity for adding a new key to a Binary Search Tree containing N keys is O(log N), though the worst-case scenario would be O(N) for an unbalanced tree.

Step-by-step explanation:

The average case time complexity of adding a new key to a Binary Search Tree (BST) containing N keys is O(log N).

When adding a key to a BST, you have to traverse the tree from the root to the correct leaf where the new key belongs. In a balanced tree, this would take logarithmic time since each comparison with a node allows you to ignore half of the remaining tree.

In practice, BSTs are not always perfectly balanced, but if they are reasonably balanced, the average case still tends to be logarithmic. However, the worst-case time complexity occurs when the BST degenerates into a linked list due to an imbalance, leading to a complexity of O(N). But since the question asks for the average case, the answer is O(log N).