Почему временная сложность вставки массива равна O (n), а не O (n + 1)?

Question

Я только начал изучать структуру данных и, проходя через вставку массива, я задавался вопросом, почему временная сложность вставки массива O (n), а не O (n + 1)?

В лучшем случае, когда вставка находится на последнем месте, сложность времени - O (1). Я предполагаю, что мы рассматриваем 1 для вставки элемента, поскольку здесь не перемещаются никакие элементы. В худшем случае, Учитывая, что нам нужно переместить n элементов, а затем вставить новый элемент. Должна ли быть временной сложностью O (n + 1)? n для перемещения элементов и 1 для вставки.

Помощь очень ценится. Спасибо.

Answer 1

Любая функция, которая является O (n), также является O (n + 1) и наоборот. Члены нижнего порядка по существу игнорируются, поэтому +1 не вносит ничего значимого.