Modulo-N counter in Verilog - Time & Space Complexity

Time Complexity: Modulo-N counter

O(N)

Understanding Time Complexity

We want to understand how the time it takes for a modulo-N counter to run changes as the size of N changes.

Specifically, how does the number of steps grow when the counter counts up to N?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module modulo_n_counter #(
  parameter int N = 16
) (
  input logic clk,
  input logic reset,
  output logic [$clog2(N)-1:0] count
);

always_ff @(posedge clk or posedge reset) begin
  if (reset) count <= 0;
  else if (count == N-1) count <= 0;
  else count <= count + 1;
end
endmodule

This code counts from 0 up to N-1, then resets back to 0, repeating continuously.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counter increments by 1 on each clock cycle.
• How many times: It repeats counting up to N times before resetting.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (N)	Approx. Operations (increments)
10	10 increments before reset
100	100 increments before reset
1000	1000 increments before reset

Pattern observation: The number of increments grows directly with N. If N doubles, the count steps double too.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete one full count grows linearly as N gets bigger.

Common Mistake

[X] Wrong: "The counter runs in constant time because it just increments once per clock."

[OK] Correct: While each increment is quick, the total time to count all the way to N depends on N itself, so it grows as N grows.

Interview Connect

Understanding how counters scale helps you reason about timing and performance in hardware design, a useful skill in many real-world projects.

Self-Check

"What if we changed the counter to increment by 2 each time instead of 1? How would the time complexity change?"