Pop Operation on Stack in DSA C - Time & Space Complexity

Time Complexity: Pop Operation on Stack

O(1)

Understanding Time Complexity

We want to understand how long it takes to remove an item from a stack.

Specifically, how the time changes as the stack grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Remove top item from stack if not empty
int pop(Stack* s) {
    if (s->top == -1) {
        return -1; // stack empty
    }
    int item = s->arr[s->top];
    s->top--;
    return item;
}
    

This code removes the top element from the stack and returns it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and removing the top element.
• How many times: Exactly once per pop call.

How Execution Grows With Input

Each pop removes one item with a fixed number of steps.

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

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

Final Time Complexity

Time Complexity: O(1)

This means popping an item takes the same short time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Pop takes longer if the stack is bigger because it has to look through all items."

[OK] Correct: Pop only removes the top item directly without checking others, so size does not affect time.

Interview Connect

Knowing that pop is very fast helps you understand stack efficiency and shows you can analyze simple but important operations clearly.

Self-Check

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