Evaluate Postfix Expression Using Stack in DSA C - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We analyze how the time needed to evaluate a postfix expression changes as the expression gets longer.

We want to know how the number of steps grows with the size of the expression.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int evaluatePostfix(char* expr) {
    Stack s;
    initStack(&s); // Initialize the stack before use
    for (int i = 0; expr[i] != '\0'; i++) {
        if (isdigit(expr[i])) {
            push(&s, expr[i] - '0');
        } else {
            int val2 = pop(&s);
            int val1 = pop(&s);
            push(&s, applyOp(val1, val2, expr[i]));
        }
    }
    return pop(&s);
}
    

This code evaluates a postfix expression by scanning each character once and using a stack to compute the result.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single loop scanning each character in the expression once.
• How many times: Exactly once per character in the input expression.

How Execution Grows With Input

Each character is processed once, so the total steps grow directly with expression length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows linearly as the expression gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows in direct proportion to the length of the postfix expression.

Common Mistake

[X] Wrong: "Because of the stack operations, the time complexity is more than linear, maybe quadratic."

[OK] Correct: Each character is pushed or popped at most once, so stack operations add only constant work per character, keeping the total time linear.

Interview Connect

Understanding this linear time complexity shows you can analyze how simple data structures like stacks help solve problems efficiently, a key skill in interviews.

Self-Check

"What if the expression included multi-digit numbers separated by spaces? How would the time complexity change?"