Question

Consider a SET of int... add, rem, member are the ops... if we implement this as a balanced BST (let's say an AVL tree), what is the time complexity (worst case) of the MEMBER operation?

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

Answer 1

The time complexity of the MEMBER operation in a balanced BST (such as an AVL tree) is O(log n) in the worst case.

Step-by-step explanation:

The time complexity of the MEMBER operation in a balanced BST (such as an AVL tree) is O(log n) in the worst case.

This means that the time taken to find a specific element in the BST increases logarithmically with the number of elements in the tree.

For example, if you have a balanced BST with 1000 elements, it would take at most 10 comparisons (log21000 = 10) to find a specific element using the MEMBER operation.