DMA controller on bus in ARM Architecture - Time & Space Complexity

Time Complexity: DMA controller on bus

O(n)

Understanding Time Complexity

We want to understand how the time taken by a DMA controller to transfer data changes as the amount of data grows.

Specifically, how does the number of operations scale when the DMA moves more data over the bus?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet controlling a DMA transfer.

    MOV R0, #0          ; Start address
    MOV R1, #N          ; Number of bytes to transfer
DMA_START:
      LDRB R2, [R0], #1 ; Load byte from source and increment pointer
      STRB R2, [DMA_REG]; Store byte to DMA register
      SUBS R1, R1, #1   ; Decrement count
      BNE DMA_START     ; Repeat until all bytes transferred
    

This code moves N bytes from memory to the DMA register one by one.

Identify Repeating Operations

Look for the repeated steps in the code.

• Primary operation: Loading and storing one byte per loop cycle.
• How many times: Exactly N times, once for each byte.

How Execution Grows With Input

As the number of bytes N increases, the loop runs more times.

Input Size (n)	Approx. Operations
10	About 10 load/store cycles
100	About 100 load/store cycles
1000	About 1000 load/store cycles

Pattern observation: The number of operations grows directly with the number of bytes to transfer.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the transfer increases in a straight line as the data size grows.

Common Mistake

[X] Wrong: "The DMA transfer time stays the same no matter how much data is moved."

[OK] Correct: Each byte requires a load and store operation, so more data means more steps and more time.

Interview Connect

Understanding how DMA transfer time scales helps you reason about system performance and bottlenecks in embedded systems.

Self-Check

What if the DMA controller could transfer 4 bytes at once instead of 1? How would the time complexity change?