Case statement for multiplexing in Verilog - Time & Space Complexity

Time Complexity: Case statement for multiplexing

O(log n)

Understanding Time Complexity

We want to understand how the propagation delay of a case statement for multiplexing changes as the number of inputs grows.

In hardware, how does the critical path delay scale with the number of choices?

Scenario Under Consideration

Analyze the time complexity (propagation delay) of the following code snippet after synthesis.

module mux_case(
  input  wire [2:0] sel,
  input  wire [7:0] in0, in1, in2, in3, in4, in5, in6, in7,
  output reg  [7:0] out
);
  always @(*) begin
    case(sel)
      3'd0: out = in0;
      3'd1: out = in1;
      3'd2: out = in2;
      3'd3: out = in3;
      3'd4: out = in4;
      3'd5: out = in5;
      3'd6: out = in6;
      3'd7: out = in7;
      default: out = 8'd0;
    endcase
  end
endmodule

This code implements an 8:1 multiplexer using a case statement, which synthesizes to combinational logic.

Identify Repeating Operations

No loops or recursion; it's combinational logic synthesized to a mux tree.

• Primary operation: Parallel one-hot decoding and selection, implemented as a tree of 2:1 muxes.
• Critical path: Logarithmic number of logic levels.

How Execution Grows With Input

Synthesis tools implement large muxes as balanced trees, so delay grows logarithmically.

Input Size (n)	Approx. Logic Levels (Delay)
8	~3 levels
16	~4 levels
32	~5 levels

Pattern observation: Delay grows as O(log n) with the number of inputs.

Final Time Complexity

Time Complexity (Delay): O(log n)

The propagation delay grows logarithmically as the number of inputs increases due to the mux tree structure.

Common Mistake

[X] Wrong: "The case statement checks sequentially like software, taking O(n) time."

[OK] Correct: In hardware, all paths are evaluated in parallel; synthesis optimizes to O(log n) delay mux tree, not sequential logic.

Interview Connect

Distinguishing software-like thinking from hardware synthesis is key in digital design interviews. Explain how case synthesizes to mux trees.

Self-Check

"How does using LUTs in FPGAs affect mux delay for larger n? (Often O(1) per LUT, but still log n levels across LUTs)"