Dynamic Stack Using Resizable Array in DSA Python - Time & Space Complexity

Time Complexity: Dynamic Stack Using Resizable Array

O(1) amortized

Understanding Time Complexity

We want to understand how fast operations like push and pop run when using a stack built on a resizable array.

Specifically, how does the time to add or remove items change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following dynamic stack implementation.

class DynamicStack:
    def __init__(self):
        self.array = [None] * 2
        self.size = 0

    def push(self, value):
        if self.size == len(self.array):
            self._resize(2 * len(self.array))
        self.array[self.size] = value
        self.size += 1

    def pop(self):
        if self.size == 0:
            return None
        self.size -= 1
        value = self.array[self.size]
        self.array[self.size] = None
        if 0 < self.size <= len(self.array) // 4:
            self._resize(len(self.array) // 2)
        return value

    def _resize(self, new_capacity):
        new_array = [None] * new_capacity
        for i in range(self.size):
            new_array[i] = self.array[i]
        self.array = new_array

This code shows a stack that grows and shrinks its array size as needed.

Identify Repeating Operations

Look for loops and repeated steps that take time.

• Primary operation: Copying elements during resizing in _resize.
• How many times: Happens only when array is full or too empty, not every push/pop.

How Execution Grows With Input

Most pushes and pops take constant time, but resizing copies all elements.

Input Size (n)	Approx. Operations
10	About 10 simple steps, occasional 10-step copy
100	Mostly 100 simple steps, occasional 100-step copy
1000	Mostly 1000 simple steps, occasional 1000-step copy

Pattern observation: Most operations are quick, but resizing causes longer steps occasionally.

Final Time Complexity

Time Complexity: O(1) amortized

This means each push or pop usually takes a fixed small time, even though resizing sometimes takes longer.

Common Mistake

[X] Wrong: "Every push or pop takes time proportional to the stack size because of resizing."

[OK] Correct: Resizing happens rarely, so most operations are fast. Over many operations, the average time stays constant.

Interview Connect

Understanding amortized time helps you explain why dynamic arrays and stacks are efficient in real programs.

Self-Check

"What if we tripled the array size instead of doubling it? How would the time complexity change?"