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

Practice

1. What is the main purpose of using a state machine in an Arduino program?

easy

A. To organize the program into clear, manageable steps

B. To increase the speed of the Arduino processor

C. To reduce the power consumption automatically

D. To connect multiple Arduino boards together

Solution

1. Step 1: Understand the concept of state machines

   A state machine breaks a program into distinct states or steps to manage behavior clearly.

2. Step 2: Identify the main benefit in Arduino context

   This organization helps make the code easier to read, debug, and extend.

3. Final Answer:

   To organize the program into clear, manageable steps -> Option A

4. Quick Check:

   State machine purpose = organize steps [OK]

Hint: State machines organize code into clear steps [OK]

Common Mistakes:

• Thinking state machines speed up the processor
• Confusing power saving with state management
• Assuming state machines connect multiple boards

2. Which of the following is the correct way to declare states in an Arduino state machine using enum?

easy

A. enum State {START, RUNNING, STOPPED};

B. enum State = {START, RUNNING, STOPPED};

C. enum State {START; RUNNING; STOPPED};

D. enum State (START, RUNNING, STOPPED);

Solution

1. Step 1: Recall enum syntax in Arduino (C++)

   The correct syntax uses curly braces and commas to list states without assignment or semicolons.

2. Step 2: Check each option for syntax errors

   enum State {START, RUNNING, STOPPED}; uses correct syntax: enum State {START, RUNNING, STOPPED}; Options B, C, and D have incorrect assignment, semicolons, or parentheses.

3. Final Answer:

   enum State {START, RUNNING, STOPPED}; -> Option A

4. Quick Check:

   Correct enum syntax = enum State {START, RUNNING, STOPPED}; [OK]

Hint: Use curly braces and commas for enum states [OK]

Common Mistakes:

• Using '=' sign after enum name
• Separating states with semicolons instead of commas
• Using parentheses instead of braces

3. What will be the output on the Serial Monitor when running this Arduino code snippet?

enum State {IDLE, PROCESS, DONE};
State currentState = IDLE;

void setup() {
  Serial.begin(9600);
  switch(currentState) {
    case IDLE:
      Serial.println("Waiting");
      break;
    case PROCESS:
      Serial.println("Working");
      break;
    case DONE:
      Serial.println("Finished");
      break;
  }
}

medium

A. Finished

B. Working

C. Waiting

D. No output

Solution

1. Step 1: Identify the initial state value

   The variable currentState is set to IDLE before setup() runs.

2. Step 2: Follow the switch-case logic

   Switch checks currentState; since it is IDLE, it prints "Waiting" to Serial Monitor.

3. Final Answer:

   Waiting -> Option C

4. Quick Check:

   State IDLE prints "Waiting" [OK]

Hint: Check initial state value to predict output [OK]

Common Mistakes:

• Assuming PROCESS or DONE prints without state change
• Thinking setup() runs multiple times
• Ignoring break statements in switch

4. Identify the error in this Arduino state machine code snippet:

enum State {START, RUNNING, STOPPED};
State currentState = START;

void loop() {
  switch(currentState) {
    case START:
      Serial.println("Start");
      currentState = RUNNING
      break;
    case RUNNING:
      Serial.println("Running");
      break;
    case STOPPED:
      Serial.println("Stopped");
      break;
  }
}

medium

A. Incorrect enum declaration

B. Serial not initialized in setup()

C. Missing break in RUNNING case

D. Missing semicolon after currentState = RUNNING

Solution

1. Step 1: Check syntax line by line

   Look at the line: currentState = RUNNING without a semicolon at the end.

2. Step 2: Identify the error type

   Missing semicolon causes a compile error. Other parts are correct or not critical for this snippet.

3. Final Answer:

   Missing semicolon after currentState = RUNNING -> Option D

4. Quick Check:

   Missing semicolon = syntax error [OK]

Hint: Check each statement ends with a semicolon [OK]

Common Mistakes:

• Ignoring missing semicolon errors
• Assuming enum declaration is wrong
• Forgetting to initialize Serial in setup()

5. You want to design a state machine for an Arduino traffic light with states: RED, GREEN, YELLOW. Which approach correctly updates the state to cycle through RED -> GREEN -> YELLOW -> RED inside loop()?

hard

A. Use a while loop inside loop() to cycle states infinitely

B. Use a switch on currentState and set currentState to the next state in each case

C. Use if statements comparing currentState to integers 0,1,2 and increment currentState by 1

D. Use delay() to wait and then reset currentState to RED always

Solution

1. Step 1: Understand state machine cycling

   Using a switch-case on currentState allows clear, readable transitions between states.

2. Step 2: Evaluate each option's suitability

   Use a switch on currentState and set currentState to the next state in each case correctly updates currentState to the next state inside each case. Use if statements comparing currentState to integers 0,1,2 and increment currentState by 1 uses integers but lacks clarity and safe cycling. Use a while loop inside loop() to cycle states infinitely with while loop inside loop() blocks Arduino's main loop. Use delay() to wait and then reset currentState to RED always resets state always to RED, not cycling properly.

3. Final Answer:

   Use a switch on currentState and set currentState to the next state in each case -> Option B

4. Quick Check:

   Switch-case for cycling states = Use a switch on currentState and set currentState to the next state in each case [OK]

Hint: Use switch-case to update states clearly [OK]

Common Mistakes:

• Using while loops inside loop() causing freezes
• Resetting state without cycling
• Using integers without clear state names