Stack Implementation Using Array in DSA Python - Time & Space Complexity

Time Complexity: Stack Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run when using an array.

How does the time to push or pop change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Stack:
    def __init__(self, capacity):
        self.array = [None] * capacity
        self.top = -1
        self.capacity = capacity

    def push(self, value):
        if self.top == self.capacity - 1:
            return False  # stack full
        self.top += 1
        self.array[self.top] = value
        return True

    def pop(self):
        if self.top == -1:
            return None  # stack empty
        value = self.array[self.top]
        self.top -= 1
        return value

This code creates a stack using an array and supports push and pop operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single step assignments and index updates in push and pop.
• How many times: Each push or pop runs once per call, no loops inside.

How Execution Grows With Input

Each push or pop does a fixed number of steps regardless of stack size.

Input Size (n)	Approx. Operations
10	4 steps per push/pop
100	4 steps per push/pop
1000	4 steps per push/pop

Pattern observation: The time stays the same no matter how big the stack is.

Final Time Complexity

Time Complexity: O(1)

This means each push or pop takes the same short time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack grows because the array is bigger."

[OK] Correct: The code only changes one position in the array each time, so the size does not affect the time.

Interview Connect

Knowing that stack operations run in constant time helps you explain why stacks are efficient for many tasks like undo or expression evaluation.

Self-Check

"What if the array needs to resize dynamically when full? How would the time complexity change?"