যে বাংলাদেশি সর্বশেষ ম্যাগসেসে পুরস্কার পেয়েছেন?

Question:

What is the worst-case time complexity of searching for an element in a balanced Binary Search Tree (BST) containing n nodes?

Options:

        
• A) O(1)
        
• B) O(log n)
        
• C) O(n)
        
• D) O(n log n)
    

Correct Answer: B) O(log n)

Detailed Explanation:

In a balanced Binary Search Tree (such as an AVL tree or a Red-Black tree), the height of the tree is strictly bounded by O(log n).

        
• During each comparison, the search space is effectively halved by deciding whether to traverse down the left subtree or the right subtree.
        
• In the worst-case scenario, the search continues all the way from the root node to a leaf node at the maximum depth.
        
• Since the maximum depth (height) of a balanced BST with n nodes is log2(n), the maximum number of comparisons performed is proportional to O(log n).
    

Why Other Options Are Incorrect:

        
• A) O(1): Constant time is characteristic of direct hash table lookups under optimal conditions, not tree-based search structures.
        
• C) O(n): This represents the worst-case complexity of a skewed (unbalanced) BST resembling a linked list, but the problem explicitly states the tree is balanced.
        
• D) O(n log n): This time complexity is typical of efficient sorting algorithms (like Merge Sort or Heap Sort), not an element search operation.