Why state machines are used in embedded in Embedded C - Performance Analysis

Time Complexity: Why state machines are used in embedded

O(n)

Understanding Time Complexity

We want to understand how using state machines affects the time it takes for embedded programs to run.

Specifically, we ask: how does the program's work grow as it handles more inputs or states?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    enum State {IDLE, PROCESS, DONE};
    enum State current_state = IDLE;

    void run_state_machine(int input) {
      switch(current_state) {
        case IDLE:
          if(input > 0) current_state = PROCESS;
          break;
        case PROCESS:
          // do some processing
          current_state = DONE;
          break;
        case DONE:
          // finish up
          current_state = IDLE;
          break;
      }
    }
    

This code shows a simple state machine switching between states based on input and actions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The state check and transition inside the switch-case.
• How many times: Each call to run_state_machine runs once, but it is called repeatedly as inputs arrive.

How Execution Grows With Input

Each input causes one state check and possibly a state change.

Input Size (n)	Approx. Operations
10	10 state checks and transitions
100	100 state checks and transitions
1000	1000 state checks and transitions

Pattern observation: The work grows directly with the number of inputs, one step per input.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows in a straight line with how many inputs come in.

Common Mistake

[X] Wrong: "State machines make the program run slower because they add extra steps."

[OK] Correct: State machines organize work clearly, so each input is handled in a simple step, not slowing down overall processing.

Interview Connect

Understanding how state machines keep processing simple and predictable helps you explain how embedded systems handle tasks efficiently.

Self-Check

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