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

Time Complexity: Infix to Postfix Conversion Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time taken to convert an infix expression to postfix grows as the expression gets longer.

Specifically, how does the number of steps change when the input expression size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def infix_to_postfix(expression):
    stack = []
    result = ''
    for char in expression:
        if char.isalnum():
            result += char
        elif char == '(': 
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(': 
                result += stack.pop()
            stack.pop()
        else:
            while stack and precedence(stack[-1]) >= precedence(char):
                result += stack.pop()
            stack.append(char)
    while stack:
        result += stack.pop()
    return result

This code converts an infix expression (like "a+b*c") to postfix notation (like "abc*+") using a stack to manage operators.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One main loop that goes through each character of the input expression once.
• How many times: Exactly once for each character in the expression (n times).
• Inside this loop, there are some smaller loops that pop from the stack, but each operator is pushed and popped only once in total.

How Execution Grows With Input

As the expression length grows, the number of steps grows roughly in direct proportion.

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

Pattern observation: The total work grows linearly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows in a straight line with the length of the expression.

Common Mistake

[X] Wrong: "Because there are nested loops, the time must be quadratic O(n²)."

[OK] Correct: The inner loops only pop operators that were pushed once, so total operations still add up to a single pass over the input and stack, keeping it linear.

Interview Connect

Understanding this linear time complexity helps you explain why stack-based expression parsing is efficient and practical in real coding tasks.

Self-Check

"What if the input expression contains multi-digit numbers or variables with multiple letters? How would the time complexity change?"