Ring buffer for UART receive in Embedded C - Time & Space Complexity

Time Complexity: Ring buffer for UART receive

O(n)

Understanding Time Complexity

We want to understand how the time to process UART data grows as more bytes arrive.

How does the ring buffer handle incoming data efficiently as input size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define BUFFER_SIZE 128
volatile uint8_t ring_buffer[BUFFER_SIZE];
volatile uint16_t head = 0;
volatile uint16_t tail = 0;

void uart_receive_byte(uint8_t data) {
    ring_buffer[head] = data;
    head = (head + 1) % BUFFER_SIZE;
}
    

This code stores each received byte into a ring buffer and moves the head pointer forward.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Storing one byte and updating the head index.
• How many times: Once per received byte, repeated as many bytes arrive.

How Execution Grows With Input

Each new byte causes one store and one index update, so work grows directly with bytes received.

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

Pattern observation: Operations increase linearly as more bytes arrive.

Final Time Complexity

Time Complexity: O(n)

This means the time to process data grows directly in proportion to the number of bytes received.

Common Mistake

[X] Wrong: "The ring buffer processes all bytes at once, so time does not grow with input size."

[OK] Correct: Each byte triggers a store and index update, so time grows with each byte received, not all at once.

Interview Connect

Understanding how data structures like ring buffers handle input efficiently shows your grasp of real-time data processing.

Self-Check

"What if the ring buffer size doubled? How would the time complexity change when receiving bytes?"