Which one of the following is the tightest upper bound on the time complexity…

Concept

Inserting a key into a binary search tree (BST) follows a single root-to-leaf path: at each node we compare and move left or right until we reach an empty spot. The work is therefore proportional to the height of the tree h. An upper bound must hold for the worst case over all possible insertion orders, so we must use the largest height the tree can attain.

Application

1. The cost of one insertion equals the number of nodes visited on the search path, which is at most the height h.

2. In the worst case the keys arrive already sorted (e.g. 1, 2, 3, ...). Each new key is larger than every existing key, so the tree degenerates into a single right-leaning chain.

3. A chain of n nodes has height h = n, so the search path can be as long as n comparisons.

4. Therefore the tightest guaranteed upper bound for a single insertion is O(n).

Cross-check

• O(log n) is achieved only when the tree stays balanced (height ~ log n). A plain BST gives no balance guarantee, so log n cannot serve as an upper bound for every case.

• O(n) covers both the balanced case and the skewed worst case, and the skewed case actually reaches it, so it is the tightest bound that always holds.