Which of the following is TRUE ?
2023
Which of the following is TRUE ?
- A.
The cost of searching an AVL tree is
\(\theta (log \ n)\)but that of binary search is\(O(n)\) - B.
The cost of searching an AVL tree in
\(\theta (log \ n)\)but that of complete binary tree is\(\theta(n \ log \ n)\) - C.
The cost of searching a binary tree is
\(o(log \ n)\)but that of AVL tree is\(\theta(n)\) - D.
The cost of searching an AVL tree is
\(\theta(n \ log \ n)\)but that of binary search tree is\(O(n)\)
Attempted by 582 students.
Show answer & explanation
Correct answer: A
Correct statement: The cost of searching an AVL tree is Θ(log n) but the cost of searching a binary search tree can be O(n) in the worst case.
AVL tree: Because AVL trees maintain a height-balance property, their height is O(log n). Therefore search follows the height and takes Θ(log n).
Unbalanced binary search tree: If insertions produce a degenerate (chain) shape, the height becomes n and search takes O(n) in the worst case. The average-case for a randomly-built BST can be Θ(log n), but that is not guaranteed.
Clarification: The term "binary search" often refers to the array binary-search algorithm, which runs in Θ(log n) on sorted arrays. In this question the intended comparison is with a binary search tree (BST).
Therefore, the statement asserting an AVL search cost of Θ(log n) and a binary search tree search cost of O(n) in the worst case is correct. The other given statements are incorrect because they claim wrong complexities such as Θ(n log n), o(log n), or Θ(n) for AVL search.