যুক্তরাষ্ট্রের কোন প্রেসিডেন্ট অভিনেতা ছিলেন?

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)

Explanation:

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

During a search operation:

    
• At each step, the search compares the target value with the current node's value.
    
• Based on the comparison, it eliminates half of the remaining subtree.
    
• In the worst case, the search traverses from the root to the deepest leaf node, which requires a number of comparisons equal to the height of the tree.

Why Other Options are Incorrect:

    
• Option A [O(1)]: Constant time is typical for hash table lookups in the average case, not tree traversals.
    
• Option C [O(n)]: Linear time occurs in an unbalanced or degenerate BST (which resembles a linked list), but the question specifies a balanced BST.
    
• Option D [O(n log n)]: This complexity is common for efficient comparison-based sorting algorithms (like Merge Sort or Heap Sort), not single-element search operations.