Question

The time-complexity of searching an AVL tree is in the worst case and in the average case. On), On) O(logot). O(log O ON), C(n) 0(), O(log) Question 16 2 pts The time-complexity of searching a binary search tree is in the worst case and in the average case (1), O(log) O(logn), O(log,n) On), On) 001), 001)

Answer 1

1. (B) O(log₂n), O(log₂n)

The worst case and average case time complexity of Searching in AVL trees is O(log₂n). It is a binary search tree with height difference of left and right sub tree of any node can not be more than 1.

2. (A) O(n), O(log₂n)

The worst case complexity of binary search tree is O(n) since height can be equal to number of nodes since all nodes can be in same sub tree side in worst case and the time complexity is O(h) where h is height of tree. In average case, the time complexity is O(log₂n)