Event-driven state machine in Embedded C - Time & Space Complexity

Time Complexity: Event-driven state machine

O(n)

Understanding Time Complexity

We want to understand how the time taken by an event-driven state machine changes as it processes more events.

How does the number of events affect the work done inside the state machine?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple event-driven state machine
void process_event(int event) {
    switch(current_state) {
        case STATE_IDLE:
            if(event == EVENT_START) {
                current_state = STATE_RUNNING;
            }
            break;
        case STATE_RUNNING:
            if(event == EVENT_STOP) {
                current_state = STATE_IDLE;
            }
            break;
    }
}
    

This code changes the state based on the event received, using a switch-case structure.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The switch-case checks the current state and event once per call.
• How many times: Once for each event processed.

How Execution Grows With Input

Each event causes one check and possibly a state change.

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

Pattern observation: The work grows directly with the number of events processed.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the number of events handled.

Common Mistake

[X] Wrong: "The state machine does a lot of work for each event, so time grows faster than the number of events."

[OK] Correct: Each event triggers only a simple check and possibly a state change, so work per event stays constant.

Interview Connect

Understanding how event-driven state machines scale helps you design responsive and efficient embedded systems.

Self-Check

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

Practice

1. What is the main purpose of an event-driven state machine in embedded C?

easy

A. To change behavior based on events and current state

B. To execute code sequentially without conditions

C. To store large amounts of data in memory

D. To perform mathematical calculations only

Solution

1. Step 1: Understand the concept of event-driven state machine

   An event-driven state machine changes its behavior depending on the current state and the events it receives.

2. Step 2: Compare options with the concept

   To change behavior based on events and current state correctly describes this behavior. Other options describe unrelated concepts.

3. Final Answer:

   To change behavior based on events and current state -> Option A

4. Quick Check:

   Event-driven state machine = change behavior by events [OK]

Hint: Remember: state machines react to events and states [OK]

Common Mistakes:

• Thinking state machines just run code sequentially
• Confusing state machines with data storage
• Assuming state machines only do math

2. Which of the following is the correct way to define states in an event-driven state machine using embedded C?

easy

A. int STATE_IDLE = 0; int STATE_RUN = 1; int STATE_STOP = 2;

B. #define STATE_IDLE 0 #define STATE_RUN 1 #define STATE_STOP 2

C. typedef enum {STATE_IDLE, STATE_RUN, STATE_STOP} State;

D. char* states[] = {"IDLE", "RUN", "STOP"};

Solution

1. Step 1: Identify proper enum syntax in embedded C

   Using typedef enum with named states is the standard and clear way to define states.

2. Step 2: Check options for correctness and clarity

   The typedef enum syntax is the preferred choice for type safety and readability. Using separate ints, #defines, or string arrays lacks these benefits and is less idiomatic.

3. Final Answer:

   typedef enum {STATE_IDLE, STATE_RUN, STATE_STOP} State; -> Option C

4. Quick Check:

   Use enum typedef for states [OK]

Hint: Use typedef enum for clear state names [OK]

Common Mistakes:

• Using #define instead of enum for states
• Using strings instead of enums for states
• Not using typedef with enum

3. Given the following code snippet, what will be the value of current_state after handle_event(EVENT_START) is called?

typedef enum {STATE_IDLE, STATE_RUN, STATE_STOP} State;
typedef enum {EVENT_START, EVENT_STOP} Event;

State current_state = STATE_IDLE;

void handle_event(Event e) {
    switch(current_state) {
        case STATE_IDLE:
            if (e == EVENT_START) current_state = STATE_RUN;
            break;
        case STATE_RUN:
            if (e == EVENT_STOP) current_state = STATE_STOP;
            break;
        case STATE_STOP:
            break;
    }
}

handle_event(EVENT_START);

medium

A. Compilation error

B. STATE_RUN

C. STATE_STOP

D. STATE_IDLE

Solution

1. Step 1: Check initial state and event

   The initial state is STATE_IDLE. The event passed is EVENT_START.

2. Step 2: Follow the switch-case logic

   In STATE_IDLE, if event is EVENT_START, current_state changes to STATE_RUN.

3. Final Answer:

   STATE_RUN -> Option B

4. Quick Check:

   EVENT_START in STATE_IDLE moves to STATE_RUN [OK]

Hint: Trace event in current state switch-case [OK]

Common Mistakes:

• Ignoring event condition inside the case
• Assuming state changes without event match
• Thinking code has syntax errors

4. Identify the bug in this event-driven state machine code snippet:

typedef enum {STATE_IDLE, STATE_RUN} State;
typedef enum {EVENT_START, EVENT_STOP} Event;

State current_state = STATE_IDLE;

void handle_event(Event e) {
    switch(current_state) {
        case STATE_IDLE:
            if (e = EVENT_START) current_state = STATE_RUN;
            break;
        case STATE_RUN:
            if (e == EVENT_STOP) current_state = STATE_IDLE;
            break;
    }
}

medium

A. State enum missing STATE_STOP

B. Missing default case in switch statement

C. current_state not initialized

D. Using assignment '=' instead of comparison '==' in if condition

Solution

1. Step 1: Inspect the if condition in STATE_IDLE case

   The condition uses 'if (e = EVENT_START)', which assigns EVENT_START to e instead of comparing.

2. Step 2: Understand the effect of assignment in condition

   Assignment returns the assigned value, which is non-zero, so condition is always true, causing incorrect state changes.

3. Final Answer:

   Using assignment '=' instead of comparison '==' in if condition -> Option D

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Check if conditions use '==' not '=' [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Ignoring missing default case (not critical here)
• Assuming all states must be defined

5. You want to add a new state STATE_PAUSE and event EVENT_PAUSE to the existing state machine. Which code snippet correctly updates the handle_event function to handle pausing from STATE_RUN and resuming back to STATE_RUN from STATE_PAUSE?

hard

A. case STATE_RUN:
if (e == EVENT_PAUSE) current_state = STATE_PAUSE;
else if (e == EVENT_STOP) current_state = STATE_IDLE;
break;
case STATE_PAUSE:
if (e == EVENT_PAUSE) current_state = STATE_RUN;
break;

B. case STATE_RUN:
if (e == EVENT_PAUSE) current_state = STATE_IDLE;
break;
case STATE_PAUSE:
if (e == EVENT_PAUSE) current_state = STATE_STOP;
break;

C. case STATE_RUN:
if (e == EVENT_STOP) current_state = STATE_PAUSE;
break;
case STATE_PAUSE:
if (e == EVENT_PAUSE) current_state = STATE_IDLE;
break;

D. case STATE_RUN:
if (e == EVENT_PAUSE) current_state = STATE_STOP;
break;
case STATE_PAUSE:
if (e == EVENT_STOP) current_state = STATE_RUN;
break;

Solution

1. Step 1: Understand desired transitions

   From STATE_RUN, EVENT_PAUSE should move to STATE_PAUSE. From STATE_PAUSE, EVENT_PAUSE should resume to STATE_RUN.

2. Step 2: Check each option for correct transitions

   case STATE_RUN: if (e == EVENT_PAUSE) current_state = STATE_PAUSE; else if (e == EVENT_STOP) current_state = STATE_IDLE; break; case STATE_PAUSE: if (e == EVENT_PAUSE) current_state = STATE_RUN; break; matches these transitions exactly. Other options assign wrong states or events.

3. Final Answer:

   case STATE_RUN: if (e == EVENT_PAUSE) current_state = STATE_PAUSE; else if (e == EVENT_STOP) current_state = STATE_IDLE; break; case STATE_PAUSE: if (e == EVENT_PAUSE) current_state = STATE_RUN; break; -> Option A

4. Quick Check:

   Pause toggles between RUN and PAUSE states [OK]

Hint: Match events to correct state transitions carefully [OK]

Common Mistakes:

• Assigning wrong states on pause/resume events
• Confusing EVENT_PAUSE with EVENT_STOP
• Missing else if for multiple events