Simple state machine with switch-case in Embedded C - Time & Space Complexity

Time Complexity: Simple state machine with switch-case

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a simple state machine changes as the input grows.

Specifically, we ask: how does the number of steps grow when the machine processes more inputs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    enum State {IDLE, RUNNING, STOPPED};
    
    void processInput(enum State *currentState, int input) {
        switch (*currentState) {
            case IDLE:
                if (input > 0) *currentState = RUNNING;
                break;
            case RUNNING:
                if (input == 0) *currentState = STOPPED;
                break;
            case STOPPED:
                // do nothing
                break;
        }
    }
    

This code changes the state based on input using a switch-case structure.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The switch-case runs once per input processed.
• How many times: It runs exactly once for each input given to the function.

How Execution Grows With Input

Each input causes one switch-case check, so the work grows directly with the number of inputs.

Input Size (n)	Approx. Operations
10	10 switch checks
100	100 switch checks
1000	1000 switch checks

Pattern observation: The number of operations grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows directly in proportion to how many inputs there are.

Common Mistake

[X] Wrong: "The switch-case runs multiple times per input, so it's slower than linear."

[OK] Correct: The switch-case runs only once per input, so the time grows linearly, not faster.

Interview Connect

Understanding how simple state machines scale helps you explain how programs handle many inputs efficiently.

Self-Check

"What if the state machine had nested loops inside each case? How would the time complexity change?"