Adder and subtractor design in VHDL - Time & Space Complexity

Time Complexity: Adder and subtractor design

O(n)

Understanding Time Complexity

We want to understand how the time to add or subtract numbers grows as the size of the numbers increases.

How does the design affect the speed when numbers get bigger?

Scenario Under Consideration

Analyze the time complexity of the following VHDL code snippet.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity AdderSubtractor is
  port(
    A, B : in unsigned(7 downto 0);
    Sel : in std_logic; -- 0 for add, 1 for subtract
    Result : out unsigned(7 downto 0)
  );
end AdderSubtractor;

architecture Behavioral of AdderSubtractor is
begin
  process(A, B, Sel) is
  begin
    if Sel = '0' then
      Result <= A + B;
    else
      Result <= A - B;
    end if;
  end process;
end Behavioral;

This code adds or subtracts two 8-bit unsigned numbers based on a select signal.

Identify Repeating Operations

Look for repeated steps inside the design.

• Primary operation: Bit-wise addition or subtraction across 8 bits.
• How many times: Each bit is processed once, but carry or borrow may propagate through all bits.

How Execution Grows With Input

As the number of bits increases, the time to complete addition or subtraction grows because carries or borrows may pass through all bits.

Input Size (bits)	Approx. Operations
8	8 bit operations, carry may ripple through 8 bits
16	16 bit operations, carry may ripple through 16 bits
32	32 bit operations, carry may ripple through 32 bits

Pattern observation: The time grows roughly linearly with the number of bits because carry or borrow can move through all bits one by one.

Final Time Complexity

Time Complexity: O(n)

This means the time to add or subtract grows in a straight line as the number of bits increases.

Common Mistake

[X] Wrong: "Addition or subtraction always takes the same time no matter how many bits there are."

[OK] Correct: Because carries or borrows can pass through all bits, larger numbers usually take longer to process.

Interview Connect

Understanding how addition and subtraction scale helps you design faster circuits and shows you can think about how hardware speed changes with input size.

Self-Check

"What if we used a carry-lookahead adder instead of a ripple-carry adder? How would the time complexity change?"