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