Stack Concept and LIFO Principle in DSA Python - Time & Space Complexity

Time Complexity: Stack Concept and LIFO Principle

O(1)

Understanding Time Complexity

We want to understand how the time to do stack operations changes as the number of items grows.

How long does it take to add or remove items from a stack?

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() if self.items else None

This code adds (push) and removes (pop) items following the last-in, first-out rule.

Identify Repeating Operations

Look at what repeats when we add or remove items.

• Primary operation: Adding or removing one item at the end of the list.
• How many times: Each push or pop does this once per call.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	1 per push or pop
100	1 per push or pop
1000	1 per push or pop

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

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes a constant amount of time, no matter the stack size.

Common Mistake

[X] Wrong: "Pushing or popping takes longer as the stack grows because there are more items."

[OK] Correct: The operations only touch the top item, so the rest of the stack size does not affect the time.

Interview Connect

Knowing that stack operations are quick and constant time helps you explain why stacks are useful for tasks like undo features or expression evaluation.

Self-Check

"What if we used a linked list instead of a list for the stack? How would the time complexity of push and pop change?"