Priority encoder in VHDL - Time & Space Complexity

Time Complexity: Priority encoder

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find the highest priority input grows as the number of inputs increases in a priority encoder.

How does the work change when we have more input signals to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

architecture Behavioral of priority_encoder is
begin
  process(inputs)
  begin
    output <= (others => '0');
    for i in inputs'range loop
      if inputs(i) = '1' then
        output <= std_logic_vector(to_unsigned(i, output'length));
        exit;
      end if;
    end loop;
  end process;
end Behavioral;

This code checks each input in order to find the first one that is high and outputs its index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that checks each input bit one by one.
• How many times: Up to n times, where n is the number of input bits.

How Execution Grows With Input

As the number of inputs grows, the process may need to check more bits before finding the first high one.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the number of inputs.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the highest priority input grows linearly as the number of inputs increases.

Common Mistake

[X] Wrong: "The priority encoder always takes the same time no matter how many inputs it has."

[OK] Correct: Because the encoder may need to check each input until it finds the first high one, so more inputs can mean more checks and more time.

Interview Connect

Understanding how the time grows with input size helps you explain how hardware or code scales, a useful skill when designing or analyzing digital circuits.

Self-Check

"What if the inputs were checked in parallel instead of one by one? How would the time complexity change?"