Stack operations (push, pop, peek) in Data Structures Theory - Time & Space Complexity

Time Complexity: Stack operations (push, pop, peek)

O(1)

Understanding Time Complexity

When working with stacks, it is important to know how fast basic actions like adding or removing items happen.

We want to understand how the time to do these actions changes as the stack grows.

Scenario Under Consideration

Analyze the time complexity of the following stack operations.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

This code shows how to add, remove, and look at the top item of a stack using a list.

Identify Repeating Operations

Each operation works on the end of the list without loops or recursion.

• Primary operation: Adding or removing one item at the end of the list.
• How many times: Each operation happens once per call, no repeated steps inside.

How Execution Grows With Input

Each push, pop, or peek takes about the same time no matter how many items are in the stack.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays constant even as the stack grows larger.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Pop or push takes longer when the stack is very big."

[OK] Correct: These operations only touch the top item, so their time does not grow with stack size.

Interview Connect

Knowing that stack operations are quick and constant time helps you explain why stacks are useful in many programs.

Self-Check

"What if the stack was implemented using a linked list instead of a list? How would the time complexity change?"