State transition table approach in Embedded C - Time & Space Complexity

Time Complexity: State transition table approach

O(n)

Understanding Time Complexity

We want to understand how the time to run a state machine using a state transition table changes as the number of states or inputs grows.

How does the program's work increase when the table or inputs get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// State transition table example
#define STATES 4
#define INPUTS 3

int state = 0;
int transition_table[STATES][INPUTS] = {
  {1, 2, 3},
  {0, 2, 3},
  {1, 0, 3},
  {3, 3, 3}
};

int process_input(int input) {
  state = transition_table[state][input];
  return state;
}
    

This code updates the current state based on the input using a fixed table of next states.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the transition table to find the next state.
• How many times: Once per input processed.

How Execution Grows With Input

Each input causes one table lookup and state update.

Input Size (n)	Approx. Operations
10	10 table lookups
100	100 table lookups
1000	1000 table lookups

Pattern observation: The work grows directly with the number of inputs processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows in a straight line as you get more inputs.

Common Mistake

[X] Wrong: "The state transition table makes the program slower as the number of states grows because it searches through all states."

[OK] Correct: The program directly accesses the next state using indexes, so it does not search or loop through states. The time per input stays constant regardless of the number of states.

Interview Connect

Understanding how state machines work with tables helps you explain efficient designs in embedded systems and shows you can reason about how code scales with input size.

Self-Check

"What if the transition table was replaced by a loop searching for the next state? How would the time complexity change?"