Ring counter in Verilog - Time & Space Complexity

Time Complexity: Ring counter

O(1)

Understanding Time Complexity

Let's see how the time it takes to run a ring counter changes as we increase its size.

We want to know how the number of steps grows when the ring counter gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module ring_counter(
  input clk,
  input reset,
  output reg [3:0] q
);
  always @(posedge clk or posedge reset) begin
    if (reset)
      q <= 4'b0001;
    else
      q <= {q[0], q[3:1]};
  end
endmodule

This code creates a 4-bit ring counter that shifts a single '1' around the bits on each clock pulse.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The bit shift operation that moves the '1' around the register.
• How many times: This happens once every clock cycle, repeating indefinitely.

How Execution Grows With Input

Each clock cycle, the ring counter shifts bits once, no matter how many bits it has.

Input Size (n bits)	Approx. Operations per cycle
4	1 shift operation
8	1 shift operation
16	1 shift operation

Pattern observation: The number of operations per clock cycle stays the same even if the ring counter size grows.

Final Time Complexity

Time Complexity: O(1)

This means the time to update the ring counter does not grow as the number of bits increases.

Common Mistake

[X] Wrong: "The time to shift bits grows with the number of bits in the ring counter."

[OK] Correct: In hardware, the shift happens in parallel, so it takes the same time regardless of size.

Interview Connect

Understanding how hardware operations scale helps you explain efficient designs clearly and confidently.

Self-Check

"What if the ring counter was implemented using a for-loop to shift bits sequentially? How would the time complexity change?"