Binary search finds an insertion position in a sorted array in O(log n). Why can the comp…

Binary search finds an insertion position in a sorted array in O(log n). Why can the complete insertion still be O(n)?

1. Later elements may all need to shift to open one array slot.
2. Binary search compares every array element after locating the position.
3. Stable sorting requires rebuilding a hash table on every insertion.