State diagram to Verilog translation - Time & Space Complexity

Time Complexity: State diagram to Verilog translation

O(n)

Understanding Time Complexity

When we translate a state diagram into Verilog code, we want to know how the time to run the code changes as the number of states grows.

We ask: How does the number of steps the hardware takes grow when we add more states?

Scenario Under Consideration

Analyze the time complexity of the following Verilog code implementing a state machine.

module fsm(
  input clk, reset,
  input in,
  output reg out
);
  typedef enum logic [1:0] {S0, S1, S2, S3} state_t;
  state_t state, next_state;

  always_ff @(posedge clk or posedge reset) begin
    if (reset) state <= S0;
    else state <= next_state;
  end

  always_comb begin
    case(state)
      S0: next_state = in ? S1 : S0;
      S1: next_state = in ? S2 : S0;
      S2: next_state = in ? S3 : S0;
      S3: next_state = S0;
      default: next_state = S0;
    endcase
    out = (state == S3);
  end
endmodule
    

This code models a simple state machine with 4 states, moving between them based on input.

Identify Repeating Operations

Look for parts that repeat as input or states grow.

• Primary operation: The state transition logic inside the always_comb block, which checks current state and input to decide next state.
• How many times: This logic runs every clock cycle, once per cycle, but the complexity depends on how many states we have to check.

How Execution Grows With Input

As the number of states n increases, the hardware must check more cases to decide the next state.

Number of States (n)	Approx. Operations per Cycle
4	4 checks
10	10 checks
100	100 checks

Pattern observation: The number of checks grows directly with the number of states.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide the next state grows linearly as the number of states increases.

Common Mistake

[X] Wrong: "The state machine runs in constant time no matter how many states it has."

[OK] Correct: Each added state means more conditions to check, so the decision logic grows with the number of states.

Interview Connect

Understanding how state machines scale helps you design efficient hardware and explain your design choices clearly in interviews.

Self-Check

"What if we replaced the case statement with a lookup table for next states? How would the time complexity change?"