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

Practice

1.

What is the main purpose of using a switch-case statement in a simple state machine?

easy

A. To create loops that repeat forever

B. To handle different states clearly and execute code based on the current state

C. To declare variables for each state

D. To stop the program immediately

Solution

1. Step 1: Understand the role of switch-case in state machines

   The switch-case statement lets the program choose what to do based on the current state value.

2. Step 2: Recognize how states are handled

   Each case corresponds to a state, so the program runs code specific to that state.

3. Final Answer:

   To handle different states clearly and execute code based on the current state -> Option B

4. Quick Check:

   switch-case manages states = To handle different states clearly and execute code based on the current state [OK]

Hint: Switch-case matches states to actions clearly [OK]

Common Mistakes:

• Thinking switch-case creates loops
• Confusing variable declaration with state handling
• Assuming switch-case stops the program

2.

Which of the following is the correct syntax for a switch statement in embedded C?

switch(state) {
  case 0:
    // code
    break;
  case 1:
    // code
    break;
  default:
    // code
}

easy

A. switch state { case 0: ... break; case 1: ... break; default: ... }

B. switch(state) { case 0: ... case 1: ... default: ... }

C. switch(state) case 0: ... break; case 1: ... break; default: ...

D. switch(state) { case 0: ... break; case 1: ... break; default: ... }

Solution

1. Step 1: Check the syntax structure of switch-case

   The switch statement requires parentheses around the variable and braces around the cases.

2. Step 2: Verify the use of colons and breaks

   Each case must have a colon and usually ends with a break to prevent fall-through.

3. Final Answer:

   switch(state) { case 0: ... break; case 1: ... break; default: ... } -> Option D

4. Quick Check:

   Correct switch-case syntax = switch(state) { case 0: ... break; case 1: ... break; default: ... } [OK]

Hint: Remember switch needs parentheses and braces [OK]

Common Mistakes:

• Omitting parentheses after switch
• Missing colons after case labels
• Forgetting break statements

3.

What will be the output of this code snippet?

int state = 1;
switch(state) {
  case 0:
    printf("State is zero\n");
    break;
  case 1:
    printf("State is one\n");
    break;
  default:
    printf("Unknown state\n");
}

medium

A. Unknown state

B. State is zero

C. State is one

D. No output

Solution

1. Step 1: Identify the value of state

   The variable state is set to 1 before the switch statement.

2. Step 2: Match the case with state value

   The switch matches case 1, so it prints "State is one" and then breaks.

3. Final Answer:

   State is one -> Option C

4. Quick Check:

   state=1 prints "State is one" [OK]

Hint: Match state value to case label to find output [OK]

Common Mistakes:

• Confusing case 0 with case 1
• Forgetting break causes fall-through
• Assuming default runs when case matches

4.

Find the error in this state machine code snippet:

int state = 0;
switch(state) {
  case 0:
    printf("Start\n");
  case 1:
    printf("Running\n");
    break;
  default:
    printf("Unknown\n");
}

medium

A. Missing break after case 0 causes fall-through

B. Switch statement missing parentheses

C. Default case should be first

D. Variable state is not initialized

Solution

1. Step 1: Check each case for break statements

   Case 0 does not have a break, so after printing "Start", it continues to case 1.

2. Step 2: Understand fall-through effect

   This causes both "Start" and "Running" to print when state is 0, which may be unintended.

3. Final Answer:

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

4. Quick Check:

   Missing break causes fall-through = Missing break after case 0 causes fall-through [OK]

Hint: Always add break after each case to avoid fall-through [OK]

Common Mistakes:

• Ignoring missing break leads to unexpected output
• Thinking default must be first case
• Assuming uninitialized variable error

5.

You want to design a simple state machine with three states: INIT (0), PROCESS (1), and DONE (2). The machine should start at INIT, then move to PROCESS, and finally to DONE. Which code snippet correctly updates the state inside the switch-case?

int state = 0;
switch(state) {
  case 0:
    // Move to PROCESS
    state = 1;
    break;
  case 1:
    // Move to DONE
    state = 2;
    break;
  case 2:
    // Finished
    break;
}

hard

A. Correctly updates state from INIT to PROCESS to DONE

B. Does not update state, stays in INIT forever

C. Skips PROCESS and goes directly to DONE

D. Causes infinite loop without state change

Solution

1. Step 1: Check state transitions in each case

   Case 0 sets state to 1 (PROCESS), case 1 sets state to 2 (DONE), case 2 does nothing (finished).

2. Step 2: Confirm the order of states

   The code moves from INIT to PROCESS to DONE in order, updating the state variable correctly.

3. Final Answer:

   Correctly updates state from INIT to PROCESS to DONE -> Option A

4. Quick Check:

   State updates follow sequence = Correctly updates state from INIT to PROCESS to DONE [OK]

Hint: Update state variable inside each case to move forward [OK]

Common Mistakes:

• Not updating state variable inside cases
• Skipping intermediate states
• Forgetting break causing unexpected behavior