Expression evaluation in Rust - Time & Space Complexity

Time Complexity: Expression evaluation

O(n)

Understanding Time Complexity

When we evaluate expressions in code, we want to know how the time it takes grows as the expression gets bigger.

We ask: How does the number of steps change when the expression has more parts?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn evaluate_expression(expr: &str) -> i32 {
    let mut stack = Vec::new();
    for ch in expr.chars() {
        if ch.is_digit(10) {
            stack.push(ch.to_digit(10).unwrap() as i32);
        } else {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();
            let res = match ch {
                '+' => a + b,
                '-' => a - b,
                '*' => a * b,
                '/' => a / b,
                _ => 0,
            };
            stack.push(res);
        }
    }
    stack.pop().unwrap()
}
    

This code evaluates a simple expression in postfix form using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the expression string.
• How many times: Once for every character in the input expression.

How Execution Grows With Input

As the expression gets longer, the code checks each character once, so the work grows steadily.

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

Pattern observation: The number of steps grows directly with the size of the expression.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Evaluating an expression always takes a lot more time because of nested operations."

[OK] Correct: Here, each character is handled once in order, so nested or not, the time grows just with expression length.

Interview Connect

Understanding how expression evaluation scales helps you explain how code handles bigger inputs clearly and confidently.

Self-Check

"What if we changed the input to include parentheses and had to handle them? How would the time complexity change?"