Memory initialization with $readmemh in Verilog - Time & Space Complexity

Time Complexity: Memory initialization with $readmemh

O(n)

Understanding Time Complexity

When we use $readmemh in Verilog, it loads data into memory from a file. We want to understand how the time it takes grows as the memory size increases.

How does the loading time change when the memory gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module memory_init;
  reg [7:0] mem [0:255];
  initial begin
    $readmemh("data.hex", mem);
  end
endmodule

This code loads 256 bytes of data from a hex file into a memory array at the start of simulation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each memory location from the file and storing it.
• How many times: Once for each memory element (256 times in this example).

How Execution Grows With Input

Loading time grows as we add more memory locations to fill.

Input Size (n)	Approx. Operations
10	10 reads and stores
100	100 reads and stores
1000	1000 reads and stores

Pattern observation: The operations increase directly with the number of memory locations.

Final Time Complexity

Time Complexity: O(n)

This means the time to load memory grows in a straight line as the memory size increases.

Common Mistake

[X] Wrong: "The loading time is constant no matter how big the memory is."

[OK] Correct: Each memory element must be read and stored, so more memory means more work and more time.

Interview Connect

Understanding how memory initialization scales helps you reason about hardware simulation and design efficiency. It shows you how data size impacts setup time, a useful skill in hardware programming.

Self-Check

"What if we used $readmemb instead of $readmemh? How would the time complexity change?"