Single-port RAM design in Verilog - Time & Space Complexity

Time Complexity: Single-port RAM design

O(1)

Understanding Time Complexity

When designing a single-port RAM in Verilog, it is important to understand how the time to access memory changes as the size of the memory grows.

We want to know how the number of operations changes when we increase the memory size.

Scenario Under Consideration

Analyze the time complexity of the following single-port RAM code snippet.

module single_port_ram (
  input wire clk,
  input wire we,
  input wire [7:0] addr,
  input wire [7:0] data_in,
  output reg [7:0] data_out
);
  reg [7:0] ram [0:255];

  always @(posedge clk) begin
    if (we) ram[addr] <= data_in;
    data_out <= ram[addr];
  end
endmodule

This code models a memory with 256 locations, each 8 bits wide, accessed through a single port for reading or writing.

Identify Repeating Operations

In this design, the main operation is accessing the memory array at a given address.

• Primary operation: Reading or writing one memory location per clock cycle.
• How many times: Once per clock cycle, regardless of memory size.

How Execution Grows With Input

Accessing memory happens in a fixed time each cycle, no matter how big the memory is.

Input Size (memory locations)	Approx. Operations per access
10	1
100	1
1000	1

Pattern observation: The time to read or write one location stays the same even if the memory size grows.

Final Time Complexity

Time Complexity: O(1)

This means each memory access takes a constant amount of time, no matter how large the memory is.

Common Mistake

[X] Wrong: "Accessing larger memory takes more time because there are more locations to check."

[OK] Correct: Memory hardware uses direct addressing, so it jumps straight to the location without checking others, keeping access time constant.

Interview Connect

Understanding that single-port RAM access time is constant helps you explain hardware efficiency clearly and confidently in interviews.

Self-Check

"What if we changed the design to a multi-port RAM allowing simultaneous accesses? How would the time complexity change?"