Which of the following is TRUE?
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
This might help..