Timing-based state machines in Arduino - Time & Space Complexity

Time Complexity: Timing-based state machines

O(1)

Understanding Time Complexity

We want to understand how the time a timing-based state machine takes grows as we add more states or longer delays.

How does the program's running time change when the state machine gets bigger or more complex?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned long previousMillis = 0;
const long interval = 1000;
int state = 0;

void loop() {
  unsigned long currentMillis = millis();
  if (currentMillis - previousMillis >= interval) {
    previousMillis = currentMillis;
    state = (state + 1) % 3;
  }
}
    

This code cycles through three states every 1000 milliseconds using timing checks instead of delays.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop() function runs repeatedly, checking the time and updating the state.
• How many times: The loop runs continuously, but the state changes only after each interval (every 1000 ms).

How Execution Grows With Input

The loop runs constantly, but the main work (state change) happens at fixed time intervals, not depending on input size.

Input Size (n)	Approx. Operations
3 states	State changes every 1000 ms, constant checks each loop
10 states	Still one check per loop, state change every 1000 ms, cycling through more states
100 states	Same pattern: constant time checks, state changes at intervals

Pattern observation: The number of states does not increase the number of operations per loop; the timing check stays constant.

Final Time Complexity

Time Complexity: O(1)

This means the time per loop cycle stays the same no matter how many states the machine has.

Common Mistake

[X] Wrong: "More states mean the program runs slower because it has to check each state every loop."

[OK] Correct: The code only checks the current state and time difference, not all states, so the time per loop stays constant.

Interview Connect

Understanding timing-based state machines helps you design efficient programs that respond well over time without slowing down as complexity grows.

Self-Check

"What if we added nested loops inside the state changes? How would the time complexity change?"

Practice

1.

What is the main purpose of using millis() in a timing-based state machine on Arduino?

easy

A. To pause the program for a fixed time

B. To reset the Arduino board

C. To track elapsed time without stopping the program

D. To read analog sensor values

Solution

1. Step 1: Understand what millis() does

   millis() returns the number of milliseconds since the Arduino started running. It keeps counting without stopping the program.

2. Step 2: Connect millis() to timing-based state machines

   Using millis() lets the program check how much time passed and change states without pausing or blocking other tasks.

3. Final Answer:

   To track elapsed time without stopping the program -> Option C

4. Quick Check:

   millis() tracks time without delay [OK]

Hint: Remember: millis() never stops your code [OK]

Common Mistakes:

• Thinking millis() pauses the program
• Confusing millis() with delay()
• Using millis() to reset Arduino

2.

Which of the following is the correct way to check if 1000 milliseconds have passed using millis()?

unsigned long previousMillis = 0;
unsigned long interval = 1000;

void loop() {
  unsigned long currentMillis = millis();
  // What condition checks if interval passed?
  if (__________) {
    // do something
    previousMillis = currentMillis;
  }
}

easy

A. previousMillis + currentMillis <= interval

B. previousMillis - currentMillis >= interval

C. currentMillis + previousMillis >= interval

D. currentMillis - previousMillis >= interval

Solution

1. Step 1: Understand elapsed time calculation

   Elapsed time is current time minus previous time: currentMillis - previousMillis.

2. Step 2: Check if elapsed time reached interval

   We compare if elapsed time is greater or equal to the interval: currentMillis - previousMillis >= interval.

3. Final Answer:

   currentMillis - previousMillis >= interval -> Option D

4. Quick Check:

   Elapsed time = current - previous [OK]

Hint: Subtract previous from current time to get elapsed [OK]

Common Mistakes:

• Reversing subtraction order
• Adding times instead of subtracting
• Using <= instead of >=

3.

What will be the output of this Arduino code snippet that uses a timing-based state machine?

unsigned long previousMillis = 0;
const long interval = 2000;
int ledState = LOW;

void setup() {
  pinMode(13, OUTPUT);
  Serial.begin(9600);
}

void loop() {
  unsigned long currentMillis = millis();
  if (currentMillis - previousMillis >= interval) {
    previousMillis = currentMillis;
    if (ledState == LOW) {
      ledState = HIGH;
    } else {
      ledState = LOW;
    }
    digitalWrite(13, ledState);
    Serial.println(ledState);
  }
}

medium

A. Prints alternating 0 and 1 every 2 seconds

B. Prints 1 continuously every 2 seconds

C. Prints 0 continuously every 2 seconds

D. No output because of syntax error

Solution

1. Step 1: Understand the timing and state toggle

   Every 2000 ms, the code toggles ledState between LOW (0) and HIGH (1).

2. Step 2: Check output printed

   Each toggle prints the current ledState (0 or 1) to Serial, alternating every 2 seconds.

3. Final Answer:

   Prints alternating 0 and 1 every 2 seconds -> Option A

4. Quick Check:

   State toggles and prints 0,1 alternately [OK]

Hint: Toggle state and print inside timed if-block [OK]

Common Mistakes:

• Assuming constant output without toggle
• Confusing HIGH/LOW with 1/0
• Missing update of previousMillis

4.

Identify the bug in this timing-based state machine code and choose the fix.

unsigned long previousMillis = 0;
const long interval = 1000;
int ledState = LOW;

void setup() {
  pinMode(13, OUTPUT);
}

void loop() {
  unsigned long currentMillis = millis();
  if (currentMillis - previousMillis > interval) {
    ledState = !ledState;
    digitalWrite(13, ledState);
  }
}

medium

A. Add previousMillis = currentMillis; inside the if-block

B. Change int ledState to bool ledState

C. Replace ! with ~ in toggle

D. Remove the if condition to toggle every loop

Solution

1. Step 1: Check timing update logic

   The code never updates previousMillis, so the condition stays true forever after first pass.

2. Step 2: Fix by updating previousMillis

   Adding previousMillis = currentMillis; inside the if-block resets the timer for the next interval.

3. Final Answer:

   Add previousMillis = currentMillis; inside the if-block -> Option A

4. Quick Check:

   Update previousMillis to reset timer [OK]

Hint: Always update previousMillis after interval check [OK]

Common Mistakes:

• Forgetting to update previousMillis
• Using bitwise NOT (~) instead of logical NOT (!)
• Removing timing check causes fast toggling

5.

You want to create a state machine that cycles through three LED states: OFF, RED, GREEN. Each state lasts 3 seconds. Which code snippet correctly implements this using millis()?

unsigned long previousMillis = 0;
const long interval = 3000;
int state = 0;

void setup() {
  pinMode(RED_PIN, OUTPUT);
  pinMode(GREEN_PIN, OUTPUT);
}

void loop() {
  unsigned long currentMillis = millis();
  if (currentMillis - previousMillis >= interval) {
    previousMillis = currentMillis;
    state = (state + 1) % 3;
    switch(state) {
      case 0:
        digitalWrite(RED_PIN, LOW);
        digitalWrite(GREEN_PIN, LOW);
        break;
      case 1:
        digitalWrite(RED_PIN, HIGH);
        digitalWrite(GREEN_PIN, LOW);
        break;
      case 2:
        digitalWrite(RED_PIN, LOW);
        digitalWrite(GREEN_PIN, HIGH);
        break;
    }
  }
}

hard

A. Does not change states due to missing update

B. Correctly cycles OFF, RED, GREEN every 3 seconds

C. Cycles states every 1 second instead of 3

D. Cycles only RED and GREEN, skipping OFF

Solution

1. Step 1: Check timing and state update

   The code uses millis() to check 3 seconds passed, then updates state cycling 0,1,2 with modulo 3.

2. Step 2: Verify LED outputs per state

   State 0 turns both LEDs off, 1 turns RED on, 2 turns GREEN on. This matches the required cycle.

3. Final Answer:

   Correctly cycles OFF, RED, GREEN every 3 seconds -> Option B

4. Quick Check:

   State cycles with modulo and timing [OK]

Hint: Use modulo (%) to cycle states smoothly [OK]

Common Mistakes:

• Forgetting to update previousMillis
• Incorrect modulo causing wrong cycles
• Not turning off LEDs in OFF state