State machine for protocol handling in Embedded C - Time & Space Complexity

Time Complexity: State machine for protocol handling

O(n)

Understanding Time Complexity

We want to understand how the time needed to run a state machine changes as the input grows.

Specifically, how many steps does the machine take when processing data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    typedef enum {IDLE, RECEIVING, PROCESSING, DONE} State;
    
    void handle_protocol(char *data, int length) {
        State current = IDLE;
        for (int i = 0; i < length; i++) {
            switch (current) {
                case IDLE:
                    if (data[i] == 'S') current = RECEIVING;
                    break;
                case RECEIVING:
                    // process data[i]
                    if (data[i] == 'E') current = PROCESSING;
                    break;
                case PROCESSING:
                    // finalize processing
                    current = DONE;
                    break;
                case DONE:
                    // finished
                    break;
            }
        }
    }
    

This code processes a data stream using a state machine with four states.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each data element once.
• How many times: Exactly once per data element, so 'length' times.

How Execution Grows With Input

As the input length grows, the number of steps grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with input size, no extra loops inside.

Final Time Complexity

Time Complexity: O(n)

This means the time to process grows in direct proportion to the input length.

Common Mistake

[X] Wrong: "Because there are multiple states, the time grows faster than the input size."

[OK] Correct: The states only change inside the single loop, so each input element is handled once, keeping growth linear.

Interview Connect

Understanding how state machines scale helps you explain how protocols handle data efficiently in real devices.

Self-Check

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