Final answer:
The AVERAGE case time complexity of the CONTAINS operation in a Binary Search Tree is O(log N).
Step-by-step explanation:
The AVERAGE case time complexity of the CONTAINS operation in a Binary Search Tree (BST) is O(log N). This means that on average, the time it takes to search for a key in a BST grows logarithmically with the number of keys, N.
Binary Search Tree is a type of data structure that organizes keys in a tree-like structure, maintaining a specific ordering property. By comparing the key being searched with the key at the root and recursively searching in the left or right subtree, the search process is able to narrow down a search space efficiently.
For example, if the BST has 1000 keys, the average number of comparisons required to find a specific key is around 10 (2^10 = 1024). This is much more efficient compared to a linear search, which would require an average of 500 comparisons (N/2) in this case.