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