602 views

Which of the following is TRUE?

1. The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
2. The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)
3. The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)
4. The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)
retagged | 602 views

A) is true as AVL tree is a balanced search tree that has time complexity of searching $\Theta ( \log n)$, but in binary search tree, we can have a completely left/right skewed tree, in which search is $O(n)$.
selected by
In an AVL tree sometimes search can succeed in first or second try. So, it should be $O(\log n)$ and not $\Theta(\log n)$ rt?

if we find the maximum height with minimum no of nodes then the height H = n/2 , without violating the property of the AVL tree . Then the cost of searching  in AVL tree could be O(n/2) . Not always necessary to be Log(n) .

Q. -> In an AVL tree sometimes search can succeed in first or second try. So, it should be O(logn) and not Θ(logn) rt?

Ans. -> Yes, You are correct. Thanks for your careful observation.

option A is right