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?"

Practice

1. Why are state machines commonly used in embedded systems?

easy

A. To reduce the physical size of the embedded device

B. To increase the clock speed of the processor

C. To organize device behavior into clear, manageable steps

D. To store large amounts of data efficiently

Solution

1. Step 1: Understand the purpose of state machines

   State machines break down complex device behavior into smaller, clear steps called states.

2. Step 2: Identify the benefit in embedded systems

   This organization helps manage complexity and makes the system easier to design and debug.

3. Final Answer:

   To organize device behavior into clear, manageable steps -> Option C

4. Quick Check:

   State machines = clear steps [OK]

Hint: State machines simplify complex behavior into steps [OK]

Common Mistakes:

• Confusing state machines with hardware speed improvements
• Thinking state machines reduce device size
• Assuming state machines store data

2. Which of the following is the correct way to represent a state machine in embedded C?

easy

A. Using a switch-case statement to handle different states

B. Using a for loop to iterate through states

C. Using a recursive function to call states

D. Using a global variable to store sensor data

Solution

1. Step 1: Identify common state machine structure

   State machines in embedded C are often implemented with switch-case to handle each state clearly.

2. Step 2: Compare other options

   For loops and recursion are not typical for state transitions; global variables store data but don't represent states.

3. Final Answer:

   Using a switch-case statement to handle different states -> Option A

4. Quick Check:

   Switch-case = state machine structure [OK]

Hint: Switch-case is classic for state handling [OK]

Common Mistakes:

• Using loops instead of switch-case for states
• Confusing recursion with state transitions
• Mixing data storage with state control

3. Consider this embedded C code snippet implementing a simple state machine:

enum State {IDLE, RUNNING, STOPPED};
State currentState = IDLE;
switch(currentState) {
  case IDLE:
    currentState = RUNNING;
    break;
  case RUNNING:
    currentState = STOPPED;
    break;
  case STOPPED:
    currentState = IDLE;
    break;
}
printf("%d", currentState);

What will be the output?

medium

A. 0

B. 1

C. 2

D. Compilation error

Solution

1. Step 1: Trace the initial state and switch

   currentState starts at IDLE (0). The switch changes it to RUNNING (1).

2. Step 2: Determine the printed value

   After the switch, currentState is RUNNING, so printf prints 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   State IDLE (0) -> RUNNING (1) printed [OK]

Hint: Follow state changes step-by-step [OK]

Common Mistakes:

• Assuming output is initial state value
• Thinking code causes error due to enum
• Confusing state values with strings

4. This embedded C code tries to implement a state machine but has a bug:

enum State {START, PROCESS, END};
State current = START;
switch(current) {
  case START:
    current = PROCESS;
  case PROCESS:
    current = END;
    break;
  case END:
    current = START;
    break;
}

What is the main problem?

medium

A. Missing break after case START causes fall-through

B. Enum values are not initialized

C. Variable current is not declared

D. Switch statement syntax is incorrect

Solution

1. Step 1: Check switch-case structure

   Case START lacks a break, so execution falls through to PROCESS case.

2. Step 2: Understand effect of missing break

   This causes current to skip PROCESS state and jump directly to END, breaking intended flow.

3. Final Answer:

   Missing break after case START causes fall-through -> Option A

4. Quick Check:

   Missing break = fall-through bug [OK]

Hint: Always add break after each case [OK]

Common Mistakes:

• Ignoring missing break causes fall-through
• Thinking enum needs explicit values
• Assuming variable declaration error

5. You want to design an embedded system that controls a traffic light with states: RED, GREEN, YELLOW. Which reason best explains why using a state machine is the best approach?

hard

A. It increases the brightness of the traffic light LEDs

B. It reduces the power consumption of the traffic light hardware

C. It allows the traffic light to store vehicle counts efficiently

D. It clearly defines each light state and transitions, making timing and control simple

Solution

1. Step 1: Identify traffic light control needs

   The system must cycle through RED, GREEN, YELLOW states in order with timing control.

2. Step 2: Understand state machine benefits

   State machines organize these states and transitions clearly, simplifying timing and logic.

3. Final Answer:

   It clearly defines each light state and transitions, making timing and control simple -> Option D

4. Quick Check:

   State machine = clear control flow [OK]

Hint: State machines map clear steps and transitions [OK]

Common Mistakes:

• Confusing state machines with hardware power savings
• Thinking state machines store data counts
• Assuming state machines affect LED brightness