edited by
11,812 views
32 votes
32 votes

Which of the following is TRUE?

  1. The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$
  2. The cost of searching an AVL tree is $\Theta (\log n)$ but that of a complete binary tree is $\Theta (n \log n)$
  3. The cost of searching a binary search tree is $O (\log n )$ but that of an AVL tree is $\Theta(n)$
  4. The cost of searching an AVL tree is $\Theta (n \log n)$ but that of a binary search tree is $O(n)$
edited by

2 Answers

Best answer
45 votes
45 votes

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)$.

edited by
Answer:

Related questions

32 votes
32 votes
2 answers
2
Ishrat Jahan asked Oct 29, 2014
12,454 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$