There are two possibilities:
- This not true, the run time is
O(nlogn)
- You know the exact implementation of SUCCESSOR, which has upper bounded logarithmic complexity (as stated,
O(logn)
), but you can deduce, that when performing it one after another it actually degenerates totheta(1)
. In fact, good implementation of SUCCESSOR in BST should have amortizedtheta(1)
complexity as each node will be visited at most twice during the wholefunc
execution.