For a balanced binary search tree with n elements, the time required to search…
2020
For a balanced binary search tree with n elements, the time required to search a given element is:
- A.
O(log n)
- B.
O(n log n)
- C.
O(n² log n)
- D.
O(n²)
Attempted by 455 students.
Show answer & explanation
Correct answer: A
Key idea: search time in a BST is proportional to the tree height, h.
Balanced/average case: the height is
O(log n), so search time isO(log n).Skewed worst case: the height can become
O(n), so search can degrade to linear time. That is why the balanced-case qualifier is important.
Answer: O(log n)