Debouncing as a state machine in Embedded C - Time & Space Complexity

Time Complexity: Debouncing as a state machine

O(n)

Understanding Time Complexity

We want to understand how the time it takes to debounce a button press grows as we check the button state repeatedly.

How does the number of checks affect the total work done by the debounce logic?

Scenario Under Consideration

Analyze the time complexity of the following debounce state machine code.

// Simple debounce state machine
#define DEBOUNCE_TIME 5

int state = 0;
int counter = 0;

void debounce_step(int button_input) {
  switch(state) {
    case 0: // waiting for press
      if(button_input) {
        state = 1; counter = 0;
      }
      break;
    case 1: // counting debounce time
      if(counter < DEBOUNCE_TIME) {
        counter++;
      } else {
        state = 2; // stable press detected
      }
      break;
    case 2: // pressed stable
      if(!button_input) {
        state = 0; // reset on release
      }
      break;
  }
}
    

This code checks the button input repeatedly and waits for a stable press by counting steps.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function debounce_step is called repeatedly in a loop to check the button state.
• How many times: It runs once per input sample, potentially many times as the button state stabilizes.

How Execution Grows With Input

Each call to debounce_step does a fixed amount of work regardless of input size.

Input Size (n)	Approx. Operations
10	10 calls x fixed steps = 10
100	100 calls x fixed steps = 100
1000	1000 calls x fixed steps = 1000

Pattern observation: The work grows directly with the number of input checks, increasing linearly.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows in a straight line as we check the button more times.

Common Mistake

[X] Wrong: "The debounce function does more work when the button is stable because it counts time."

[OK] Correct: Each call does a fixed small amount of work; counting is just a simple increment, so work per call stays the same.

Interview Connect

Understanding how repeated checks add up helps you explain how embedded systems handle noisy inputs efficiently.

Self-Check

"What if we added nested loops inside the debounce_step function to check multiple buttons? How would the time complexity change?"

Practice

1.

What is the main purpose of using debouncing in embedded C button handling?

easy

A. To avoid false triggers caused by mechanical noise

B. To speed up button press detection

C. To reduce power consumption

D. To increase button press sensitivity

Solution

1. Step 1: Understand mechanical noise in buttons

   Mechanical buttons can create multiple rapid on/off signals when pressed or released, called noise.

2. Step 2: Purpose of debouncing

   Debouncing filters out these rapid changes to detect a single clean press or release.

3. Final Answer:

   To avoid false triggers caused by mechanical noise -> Option A

4. Quick Check:

   Debouncing = Avoid false triggers [OK]

Hint: Debouncing stops noisy signals from causing multiple presses [OK]

Common Mistakes:

• Thinking debouncing speeds up detection
• Confusing debouncing with power saving
• Assuming it increases sensitivity

2.

Which of the following is the correct way to declare a state variable for a debounce state machine in embedded C?

?

easy

A. char state = 0;

B. int state = "IDLE";

C. enum ButtonState {IDLE, DEBOUNCE, PRESSED}; ButtonState state = IDLE;

D. bool state = false;

Solution

1. Step 1: Identify proper state variable type

   Using an enum clearly names states and improves code readability.

2. Step 2: Check syntax correctness

   enum ButtonState {IDLE, DEBOUNCE, PRESSED}; ButtonState state = IDLE; correctly declares an enum and initializes the state variable.

3. Final Answer:

   enum ButtonState {IDLE, DEBOUNCE, PRESSED}; ButtonState state = IDLE; -> Option C

4. Quick Check:

   Enum for states = enum ButtonState {IDLE, DEBOUNCE, PRESSED}; ButtonState state = IDLE; [OK]

Hint: Use enum for clear, readable state variables [OK]

Common Mistakes:

• Assigning string to int variable
• Using bool for multiple states
• Using char without clear meaning

3.

Given this snippet of a debounce state machine, what will be the value of state after 3 calls if the button is pressed and held?

enum State {IDLE, DEBOUNCE, PRESSED};
State state = IDLE;
int timer = 0;

void update(bool buttonPressed) {
  switch(state) {
    case IDLE:
      if(buttonPressed) {
        state = DEBOUNCE;
        timer = 2;
      }
      break;
    case DEBOUNCE:
      if(timer > 0) timer--;
      else state = PRESSED;
      break;
    case PRESSED:
      if(!buttonPressed) state = IDLE;
      break;
  }
}

// Calls:
update(true);
update(true);
update(true);

medium

A. PRESSED

B. Undefined

C. IDLE

D. DEBOUNCE

Solution

1. Step 1: Trace state changes through calls

   First call: state IDLE -> DEBOUNCE, timer=2. Second call: DEBOUNCE, timer=2>0, timer-- to 1, still DEBOUNCE. Third call: DEBOUNCE, timer=1>0, timer-- to 0, still DEBOUNCE (else not executed).

2. Step 2: Confirm final state after 3 calls

   Button is still pressed, state=DEBOUNCE (timer=0 now, changes to PRESSED on next call).

3. Final Answer:

   DEBOUNCE -> Option D

4. Quick Check:

   Timer counts down, state changes only if timer==0 at start of DEBOUNCE [OK]

Hint: Count timer ticks before state changes to PRESSED [OK]

Common Mistakes:

• Thinking PRESSED after exactly 3 calls
• Not decrementing timer
• Resetting state incorrectly

4.

Identify the bug in this debounce state machine code snippet:

enum State {IDLE, DEBOUNCE, PRESSED};
State state = IDLE;
int timer = 0;

void update(bool buttonPressed) {
  switch(state) {
    case IDLE:
      if(buttonPressed) {
        state = DEBOUNCE;
        timer = 3;
      }
      break;
    case DEBOUNCE:
      if(timer == 0) state = PRESSED;
      else timer--;
      break;
    case PRESSED:
      if(!buttonPressed) state = IDLE;
      break;
  }
}

What is the problem?

medium

A. State never changes from DEBOUNCE

B. Timer decrements after checking zero, causing one extra cycle

C. Timer is never initialized

D. Button press is ignored in PRESSED state

Solution

1. Step 1: Analyze timer decrement logic

   The code checks if timer == 0 before decrementing, so timer reaches 0 but state changes only next call.

2. Step 2: Identify effect on debounce timing

   This causes the debounce to last one extra cycle longer than intended.

3. Final Answer:

   Timer decrements after checking zero, causing one extra cycle -> Option B

4. Quick Check:

   Check timer before decrement causes delay [OK]

Hint: Decrement timer before zero check to fix timing [OK]

Common Mistakes:

• Thinking state never changes
• Ignoring timer initialization
• Assuming button ignored in PRESSED

5.

You want to implement a debounce state machine that only confirms a button press if the button is held for at least 5 cycles. Which approach below correctly implements this behavior?

enum State {IDLE, DEBOUNCE, PRESSED};
State state = IDLE;
int timer = 0;

void update(bool buttonPressed) {
  switch(state) {
    case IDLE:
      if(buttonPressed) {
        state = DEBOUNCE;
        timer = 5;
      }
      break;
    case DEBOUNCE:
      if(buttonPressed) {
        if(timer > 0) timer--;
        else state = PRESSED;
      } else {
        state = IDLE;
      }
      break;
    case PRESSED:
      if(!buttonPressed) state = IDLE;
      break;
  }
}

What happens if the button is pressed for 3 cycles then released?

hard

A. State returns to IDLE without reaching PRESSED

B. State changes to PRESSED after 3 cycles

C. State stays in DEBOUNCE indefinitely

D. State immediately changes to PRESSED on press

Solution

1. Step 1: Trace timer decrement with button held 3 cycles

   Timer starts at 5, decrements each cycle while buttonPressed is true, so after 3 cycles timer = 2.

2. Step 2: Button released before timer reaches zero

   On release, state immediately returns to IDLE without reaching PRESSED.

3. Final Answer:

   State returns to IDLE without reaching PRESSED -> Option A

4. Quick Check:

   Hold less than 5 cycles resets state [OK]

Hint: Hold button full timer cycles to reach PRESSED [OK]

Common Mistakes:

• Assuming PRESSED reached early
• Thinking DEBOUNCE lasts indefinitely
• Believing immediate PRESSED on press