Check if Stack is Empty or Full in DSA C - Time & Space Complexity

Time Complexity: Check if Stack is Empty or Full

O(1)

Understanding Time Complexity

Checking if a stack is empty or full is a common operation in stack management.

We want to know how fast these checks run as the stack size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if stack is empty
int isEmpty(int top) {
    return top == -1;
}

// Check if stack is full
int isFull(int top, int capacity) {
    return top == capacity - 1;
}
    

This code checks if the stack is empty or full by comparing the top index with limits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Simple comparison operations.
• How many times: Each check runs once per call, no loops or recursion.

How Execution Grows With Input

These checks do not depend on the stack size; they always do the same small work.

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

Pattern observation: The number of operations stays the same no matter how big the stack is.

Final Time Complexity

Time Complexity: O(1)

This means the check runs in constant time, always very fast regardless of stack size.

Common Mistake

[X] Wrong: "Checking if stack is full or empty takes longer as the stack grows."

[OK] Correct: These checks only compare two numbers, so they take the same time no matter the stack size.

Interview Connect

Understanding constant time checks like these helps you write efficient stack operations and shows you know how to reason about simple but important code.

Self-Check

"What if we changed the stack to use a linked list instead of an array? How would the time complexity of checking if it is empty or full change?"