FSM with output logic in Verilog - Time & Space Complexity

Time Complexity: FSM with output logic

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a finite state machine (FSM) with output logic changes as the input size or clock cycles increase.

Specifically, we ask: how does the number of operations grow as the FSM processes more inputs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module fsm_with_output(
  input clk, reset, in,
  output reg out
);
  typedef enum logic [1:0] {S0, S1, S2} 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: begin
        out = 0;
        next_state = in ? S1 : S0;
      end
      S1: begin
        out = 1;
        next_state = in ? S2 : S0;
      end
      S2: begin
        out = 0;
        next_state = in ? S2 : S0;
      end
    endcase
  end
endmodule

This code models a simple FSM with three states and output logic based on the current state and input.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FSM updates its state on every clock cycle.
• How many times: Once per clock cycle, repeating indefinitely as inputs arrive.

How Execution Grows With Input

Each clock cycle causes the FSM to evaluate its current state and input, then update its state and output.

Input Size (clock cycles)	Approx. Operations
10	10 state updates and output calculations
100	100 state updates and output calculations
1000	1000 state updates and output calculations

Pattern observation: The number of operations grows linearly with the number of clock cycles processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows directly in proportion to the number of clock cycles.

Common Mistake

[X] Wrong: "The FSM processes all inputs instantly regardless of input length."

[OK] Correct: Each input requires a clock cycle to update the state and output, so processing time grows with input length.

Interview Connect

Understanding how FSMs scale with input size helps you design efficient hardware and explain timing behavior clearly in interviews.

Self-Check

"What if the FSM had nested loops inside the output logic? How would the time complexity change?"