Question

Binary Search Tree containing N keys: INSERTing a new key has AVERAGE case time complexity of

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

Answer 1

The average case time complexity for inserting a new key in a binary search tree containing N keys is O(log N).

Step-by-step explanation:

The average case time complexity for inserting a new key in a binary search tree containing N keys is O(log N). This means that the time it takes to insert a new key grows logarithmically with the number of keys in the tree.

When a new key is inserted in a binary search tree, it is compared to the existing keys to determine its position in the tree. With each comparison, the search space is divided in half, resulting in a logarithmic time complexity.

For example, if you have a binary search tree with 100 keys, the average case time complexity to insert a new key would be approximately log2(100) = 6.64.