Which one of the following is the tightest upper bound that represents the…
2013
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?
- A.
\(O(1) \) - B.
\(O(log \ n) \) - C.
\(O(n)\) - D.
\(O(n \ log \ n) \)
Attempted by 571 students.
Show answer & explanation
Correct answer: C
Answer: O(n). Reason: a single insertion requires searching from the root to the insertion point. In the worst case the binary search tree is a degenerate chain with height n, so the traversal can visit up to n nodes.
Process: compare keys and follow left/right pointers until reaching the appropriate leaf position.
Worst case: tree height = n (chain) → insertion visits O(n) nodes.
Note: balanced BST variants guarantee O(log n) insertion, but the question asks for the tightest upper bound for a general BST.
A video solution is available for this question — log in and enroll to watch it.