ROM (Read-Only Memory) in Verilog - Time & Space Complexity

Time Complexity: ROM (Read-Only Memory) in Verilog

O(1)

Understanding Time Complexity

We want to understand how the time to read data from a ROM changes as the size of the memory grows.

How does the number of steps needed to get data change when the ROM size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module rom(
  input wire [3:0] addr,
  output reg [7:0] data
);
  always @(*) begin
    case(addr)
      4'd0: data = 8'hA1;
      4'd1: data = 8'hB2;
      4'd2: data = 8'hC3;
      // ... more addresses ...
      default: data = 8'h00;
    endcase
  end
endmodule

This code models a ROM that outputs a fixed 8-bit value based on a 4-bit address input.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The case statement checks the input address against stored values.
• How many times: Each read checks the address once; no loops or repeated traversals happen during a single read.

How Execution Grows With Input

Reading from ROM is like looking up a value in a fixed list by address.

Input Size (n)	Approx. Operations
10	1 check per read
100	1 check per read
1000	1 check per read

Pattern observation: The number of steps to read data stays the same no matter how big the ROM is.

Final Time Complexity

Time Complexity: O(1)

This means reading data from ROM takes the same amount of time regardless of how many entries it has.

Common Mistake

[X] Wrong: "Reading from ROM takes longer if the ROM has more data because it checks each entry one by one."

[OK] Correct: ROM uses the address directly to get data instantly, not by searching through all entries.

Interview Connect

Knowing that ROM reads are constant time helps you understand hardware design and how memory access works efficiently.

Self-Check

"What if the ROM was implemented using a loop to search for the address instead of a direct case statement? How would the time complexity change?"