сложность набора :: вставить

Я прочитал, что операция вставки в наборе занимает только log (n) время. Как это возможно?

Чтобы вставить, сначала мы должны найти местоположение в отсортированном массиве, где должен находиться новый элемент. При использовании бинарного поиска требуется log (n). Затем, чтобы вставить в это место, все последующие элементы должны быть сдвинуты на одно место вправо. Это займет еще n раз.

Мои сомнения основаны на моем понимании того, что множество реализовано в виде массива, а элементы хранятся в отсортированном порядке. Пожалуйста, поправьте меня, если мое понимание неверно.

Ответы на вопрос(2)

Ваш ответ на вопрос