Project ForgeData Structures
Trees
GATE 2013
Medium
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
- AO(1)
- BO(log n)
- O(n)
- DO(n log n)
Explanation
A plain (unbalanced) binary search tree offers no shape guarantee — in the worst case (a degenerate, linked-list-like tree), inserting requires walking all the way down its full height, which can be as large as n. O(log n) only holds for a BALANCED tree and would be violated by a skewed one, so it isn't a valid upper bound across all BSTs; the tightest bound that always holds is O(n).
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.