Traffic light controller FSM in Verilog - Time & Space Complexity

Time Complexity: Traffic light controller FSM

O(1)

Understanding Time Complexity

We want to understand how the time it takes for a traffic light controller FSM to run changes as the system grows.

Specifically, we ask: how does the number of steps grow when the input or states increase?

Scenario Under Consideration

Analyze the time complexity of the following Verilog FSM code.

module traffic_light_controller(
  input clk, reset,
  output reg [1:0] light_state
);
  parameter RED=2'd0, GREEN=2'd1, YELLOW=2'd2;
  reg [1:0] state, next_state;

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

  always @* begin
    case(state)
      RED: next_state = GREEN;
      GREEN: next_state = YELLOW;
      YELLOW: next_state = RED;
      default: next_state = RED;
    endcase
  end

  always @* begin
    light_state = state;
  end
endmodule

This code cycles through traffic light states: RED, GREEN, YELLOW, then back to RED.

Identify Repeating Operations

The FSM updates its state on every clock cycle.

• Primary operation: State transition on each clock tick.
• How many times: Once per clock cycle, indefinitely.

How Execution Grows With Input

The FSM runs one state update per clock cycle regardless of input size.

Input Size (n)	Approx. Operations
10	10 state updates
100	100 state updates
1000	1000 state updates

Pattern observation: The number of operations grows linearly with time, but each update is constant work.

Final Time Complexity

Time Complexity: O(1)

This means each state update takes the same fixed time, no matter how many states or inputs there are.

Common Mistake

[X] Wrong: "The FSM takes longer as more states are added because it checks all states each time."

[OK] Correct: The FSM only moves from one state to the next directly, so each update is a simple step, not a full search.

Interview Connect

Understanding FSM time complexity helps you explain how hardware designs handle timing predictably and efficiently.

Self-Check

"What if the FSM had to check multiple inputs before deciding the next state? How would the time complexity change?"