What is the average-case time complexity of searching for a key in a binary search tree built from random insertions?
Correct answer D. O(log n)
Explanation
Random insertion order produces a tree whose expected height is proportional to log n, and a search follows a single root-to-leaf path, so on average it costs O(log n) comparisons. The worst case is O(n), reached when keys arrive in sorted order and the tree degenerates into a chain. Constant-time lookup is the average for hash tables, not trees.
Answer checked How we write and check questions
Discussion