Infix to Postfix Conversion Using Stack in DSA C - Time & Space Complexity

Time Complexity: Infix to Postfix Conversion Using Stack

O(n)

Understanding Time Complexity

We analyze how the time needed to convert an infix expression to postfix grows as the expression gets longer.

We want to know how the number of steps changes when the input expression size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s);
    int i = 0, k = 0;
    while (infix[i] != '\0') {
        if (isOperand(infix[i])) {
            postfix[k++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[k++] = pop(&s);
            }
            pop(&s); // remove '('
        } else {
            while (!isEmpty(&s) && precedence(peek(&s)) > precedence(infix[i])) {
                postfix[k++] = pop(&s);
            }
            push(&s, infix[i]);
        }
        i++;
    }
    while (!isEmpty(&s)) {
        postfix[k++] = pop(&s);
    }
    postfix[k] = '\0';
}
    

This code converts an infix expression to postfix using a stack to handle operators and parentheses.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single while loop scanning each character of the input expression once.
• How many times: Once per character in the input (n times), plus popping remaining operators from the stack at the end.

How Execution Grows With Input

As the input expression length grows, the code processes each character once, with some extra steps for operators.

Input Size (n)	Approx. Operations
10	About 10 main steps plus some stack operations
100	About 100 main steps plus stack operations proportional to operators
1000	About 1000 main steps plus stack operations proportional to operators

Pattern observation: The total steps grow roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows linearly with the length of the input expression.

Common Mistake

[X] Wrong: "The nested while loops make this algorithm quadratic time O(n²)."

[OK] Correct: Each character is pushed and popped at most once, so total operations stay proportional to n, not n squared.

Interview Connect

Understanding this linear time conversion shows you can handle stack-based parsing efficiently, a useful skill in many coding problems.

Self-Check

"What if the input expression included multi-digit numbers or variables? How would the time complexity change?"