Сложность реализации стека динамическим массивом

В типичной реализации динамического массива мы удваиваем стек, когда нет места для нового элемента. В этом случае удвоения среднее время операции push равно O (n).

Какова сложность пуша, если вместо удвоения мы увеличим размер стека на (n + k)?

Мой подход следующий

Предполагая, что стек был пуст и k = 10, увеличиваем стек до 10 элементов. После 10 элементов делаем 20 элементов и так далее.

Среднее время копирования элементов вокруг составляет 10 + 20 + 30 + ...

Значит, среднее время для выталкивания должно быть порядка O (n)?

Правильно ли мой подход?

5
задан Gilles 'SO- stop being evil' 16 September 2012 в 20:32
поделиться