পাষাণ আমাদের কী শিক্ষা দেয়?

Question:

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

Options:

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

Correct Answer: B) O(log n)

Explanation:

A Binary Search Tree (BST) maintains the property that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger.

    
• Why B is correct: In a balanced BST (such as an AVL tree or Red-Black tree), the height of the tree is strictly bounded by O(log n). Because each comparison allows the algorithm to discard half of the remaining nodes, the search path from the root to any leaf takes at most O(log n) steps in the worst case.
    
• Why A is incorrect: Constant time O(1) lookup is characteristic of ideal hash tables, not tree-based structures where traversal is required.
    
• Why C is incorrect: A time complexity of O(n) occurs in an unbalanced (skewed) BST where the tree degrades into a linked list. However, the problem explicitly specifies that the tree is balanced.
    
• Why D is incorrect: O(n log n) is typically the time complexity for sorting algorithms (such as Merge Sort or Heap Sort), not single-element lookup.