Which of the following is TRUE ?

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) 07 Dec 2023 Official Paper

The cost of searching an AVL tree is θ (log n) but that of binary search is 0(n)
The cost of searching an AVL tree in θ (log n) but that of complete binary tree is θ (n log n)
The cost of searching a binary tree is 0 (log n) but that of AVL tree is θ (n)
The cost of searching an AVL tree is θ (n log n) but that of binary search tree is θ (n)

Answer 1

The correct answer is The cost of searching an AVL tree is θ (log n) but that of binary search is 0(n)

EXPLANATION:

AVL trees are a type of self-balancing binary search tree. The time complexity for search, insert, and delete operations in an AVL tree is O(log n), where "n" is number of nodes in the tree.
This is because AVL trees ensure that the tree remains balanced, thus keeping the height at log n.
On the other hand, a binary search tree (not necessarily balanced) could degenerate into something similar to a linked list in the worst-case scenario, leading to a time complexity of O(n) for aforementioned operations.
The statement jumbles up terminologies a bit; binary search typically refers to an operation performed on sorted arrays rather than trees, and that indeed has a time complexity of O(log n). But if we understand that it's referring to a binary search tree, the statement is correct.

The other options incorrectly state the time complexities for AVL and binary trees.