What is the worst-case time complexity of inserting an element into a sorted…

Concept: Inserting an element into a sorted array (rather than appending to an unsorted one) has two separable costs: (1) locating the correct position, and (2) making room for the new element by shifting the elements that must move out of the way. The overall time complexity is governed by whichever of these two costs dominates.

1. Locate the position: because the array is sorted, binary search finds the correct insertion index in O(log n) comparisons.

2. Make room: every element from the insertion index onward must be shifted one slot to the right before the new value can be written in. In the worst case the position is at (or near) the front of the array, so up to n elements must shift, which costs O(n).

3. Combine the two costs: total work is O(log n) + O(n). Since O(n) dominates O(log n) for large n, the overall worst-case time complexity of the insertion is O(n).

Cross-check: consider inserting at the far end of the array instead of the front. If the correct sorted position for the new value is the last slot, no existing element needs to move — that placement costs O(1) plus the O(log n) search, which is cheaper than the front-insertion case, not more expensive. So placement at the end never produces a larger shift cost than placement at the front; the worst case remains the scenario where the maximum number of elements must be shifted, which is O(n).