Down counter design in Verilog - Time & Space Complexity

Time Complexity: Down counter design

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a down counter to run changes as the count size changes.

How does the number of steps grow when the counter counts down from a bigger number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module down_counter(
  input wire clk,
  input wire rst,
  output reg [3:0] count
);

always @(posedge clk or posedge rst) begin
  if (rst)
    count <= 4'd10;
  else if (count > 0)
    count <= count - 1;
end
endmodule

This code counts down from 10 to 0, decreasing the count by 1 each clock cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The count decreases by 1 every clock cycle.
• How many times: The operation repeats once per clock cycle until count reaches zero.

How Execution Grows With Input

Each step reduces the count by one, so the total steps equal the starting count.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The number of steps grows directly with the starting count size.

Final Time Complexity

Time Complexity: O(n)

This means the time to count down grows in a straight line with the starting number.

Common Mistake

[X] Wrong: "The counter finishes instantly regardless of the start value."

[OK] Correct: Each count step takes one clock cycle, so bigger start values take more steps and more time.

Interview Connect

Understanding how counters scale helps you reason about timing and delays in hardware designs, a useful skill in many projects.

Self-Check

What if we changed the counter to count down by 2 each step? How would the time complexity change?