The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
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)
asked in DS by Veteran (21.5k points)
retagged by | 602 views

2 Answers

+15 votes
Best answer
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)$.
answered by Veteran (11k points)
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.

Refer -> https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent

0 votes
option A is right
answered by Active (1.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,947 questions
36,793 answers
91,077 comments
34,690 users