Circular buffer DMA mode in Embedded C - Time & Space Complexity

Time Complexity: Circular buffer DMA mode

O(n)

Understanding Time Complexity

We want to understand how the time needed to process data changes when using a circular buffer with DMA in embedded C.

How does the program's work grow as the buffer size or data amount grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define BUFFER_SIZE 128
volatile uint8_t dma_buffer[BUFFER_SIZE];
volatile uint16_t write_index = 0;

void DMA_IRQHandler(void) {
    // Called when DMA transfer completes
    write_index = (write_index + 1) % BUFFER_SIZE;
    // Process new data at dma_buffer[write_index]
}
    

This code updates the write position in a circular buffer each time the DMA finishes transferring one unit of data.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Updating the write index and processing one data unit per DMA interrupt.
• How many times: Once per data unit received, repeating continuously as data arrives.

How Execution Grows With Input

Each new data unit triggers one update and processing step, so work grows directly with data amount.

Input Size (n)	Approx. Operations
10	10 updates and processing steps
100	100 updates and processing steps
1000	1000 updates and processing steps

Pattern observation: The number of operations grows linearly with the number of data units received.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle data grows directly in proportion to how much data comes in.

Common Mistake

[X] Wrong: "The circular buffer makes processing constant time regardless of data size."

[OK] Correct: Even with a circular buffer, each new data unit still needs processing, so time grows with data amount.

Interview Connect

Understanding how data handling scales with input is key in embedded systems, showing you can reason about real-time data flow efficiently.

Self-Check

"What if the DMA transfers multiple data units before triggering the interrupt? How would the time complexity change?"