Sequence detector FSM in Verilog - Time & Space Complexity

Time Complexity: Sequence detector FSM

O(n)

Understanding Time Complexity

We want to understand how the time needed to detect a sequence changes as the input grows.

How does the FSM handle longer input streams in terms of steps it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module sequence_detector(
  input clk, reset, in_bit,
  output reg detected
);
  reg [1:0] state, next_state;

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

  always @(*) begin
    case(state)
      0: next_state = (in_bit) ? 1 : 0;
      1: next_state = (in_bit) ? 1 : 2;
      2: next_state = (in_bit) ? 3 : 0;
      3: next_state = (in_bit) ? 1 : 2;
      default: next_state = 0;
    endcase
    detected = (state == 3 && in_bit);
  end
endmodule

This code detects the sequence "1101" on a stream of bits using a finite state machine.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FSM checks one input bit each clock cycle and updates its state.
• How many times: Once per input bit, so it repeats for every bit in the input stream.

How Execution Grows With Input

Each new input bit causes one state update and one check.

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

Pattern observation: The number of operations grows directly with the number of input bits.

Final Time Complexity

Time Complexity: O(n)

This means the time to detect sequences grows linearly with the input size.

Common Mistake

[X] Wrong: "The FSM checks multiple bits at once, so it runs faster than input size."

[OK] Correct: The FSM processes one bit per clock cycle, so it must check each bit in order, making time grow with input length.

Interview Connect

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

Self-Check

"What if the FSM was designed to detect multiple sequences in parallel? How would the time complexity change?"