State machine design for Arduino - Time & Space Complexity

Time Complexity: State machine design for Arduino

O(1)

Understanding Time Complexity

When designing a state machine on Arduino, it is important to understand how the program's running time scales as it processes inputs or events.

We want to know how the time spent in the code behaves as the number of states or events increases.

Scenario Under Consideration

Analyze the time complexity of the following Arduino state machine code snippet.

    enum State {IDLE, RUNNING, ERROR};
    State currentState = IDLE;

    void loop() {
      switch (currentState) {
        case IDLE:
          // wait for start
          break;
        case RUNNING:
          // perform task
          break;
        case ERROR:
          // handle error
          break;
      }
    }
    

This code switches between states and executes code based on the current state.

Identify Repeating Operations

Look for loops or repeated checks that happen every time the program runs.

• Primary operation: The switch statement checking the current state.
• How many times: Once every loop cycle, which runs continuously.

How Execution Grows With Input

The time to check the current state is constant regardless of the number of states because compilers optimize switch statements to jump tables for O(1) lookup.

Input Size (number of states)	Approx. Operations
3	1 lookup
10	1 lookup
100	1 lookup

Pattern observation: The number of operations remains constant regardless of the number of states.

Final Time Complexity

Time Complexity: O(1)

This means the time to decide what to do is constant, independent of the number of states.

Common Mistake

[X] Wrong: "The switch statement takes linear time because it checks each case sequentially."

[OK] Correct: In reality, compilers generate jump tables or other optimizations, so the switch runs in constant time even with more states.

Interview Connect

Understanding how state machines scale helps you design efficient embedded programs that respond quickly, a skill valuable in many real projects.

Self-Check

"What if we replaced the switch statement with a lookup table or function pointers? How would the time complexity change?"