DMA controller concept in Embedded C - Time & Space Complexity

Time Complexity: DMA controller concept

O(n)

Understanding Time Complexity

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

How does the number of data units affect the total time spent moving data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dma_transfer(int *source, int *dest, int size) {
    for (int i = 0; i < size; i++) {
        dest[i] = source[i];
    }
}
    

This code copies data from a source array to a destination array using a DMA-like loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying each element from source to destination.
• How many times: The loop runs once for each element, so exactly size times.

How Execution Grows With Input

As the number of data elements increases, the total copy operations increase at the same rate.

Input Size (n)	Approx. Operations
10	10 copy operations
100	100 copy operations
1000	1000 copy operations

Pattern observation: The time grows directly with the number of elements; doubling elements doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the transfer grows in a straight line with the amount of data.

Common Mistake

[X] Wrong: "DMA transfers all data instantly, so time does not depend on data size."

[OK] Correct: Even though DMA offloads CPU, it still moves each data unit one by one, so time grows with data size.

Interview Connect

Understanding how DMA time grows helps you explain hardware efficiency and data handling in embedded systems clearly.

Self-Check

"What if the DMA controller could transfer multiple data units at once? How would the time complexity change?"