Which of the following is TRUE?

1. AThe cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
2. BThe cost of searching an AVL tree is Θ(log n) but that of a complete binary tree is Θ(n log n)
3. CThe cost of searching a binary search tree is O(log n) but that of an AVL tree is Θ(n)
4. DThe cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)

Explanation

An AVL tree stays balanced, so search is Θ(log n). An unbalanced BST can degenerate into a chain, so its worst case is O(n).