В типичной реализации динамического массива мы удваиваем стек, когда нет места для нового элемента. В этом случае удвоения среднее время операции push равно O (n).
Какова сложность пуша, если вместо удвоения мы увеличим размер стека на (n + k)?
Мой подход следующий
Предполагая, что стек был пуст и k = 10, увеличиваем стек до 10 элементов. После 10 элементов делаем 20 элементов и так далее.
Среднее время копирования элементов вокруг составляет 10 + 20 + 30 + ...
Значит, среднее время для выталкивания должно быть порядка O (n)?
Правильно ли мой подход?