Ring buffer implementation in Embedded C - Time & Space Complexity

Time Complexity: Ring buffer implementation

O(1)

Understanding Time Complexity

We want to understand how the time it takes to run a ring buffer changes as we add more data.

Specifically, how does the number of steps grow when we insert or remove items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define BUFFER_SIZE 8

typedef struct {
  int buffer[BUFFER_SIZE];
  int head;
  int tail;
} RingBuffer;

void ring_buffer_put(RingBuffer *rb, int data) {
  rb->buffer[rb->head] = data;
  rb->head = (rb->head + 1) % BUFFER_SIZE;
}

int ring_buffer_get(RingBuffer *rb) {
  int data = rb->buffer[rb->tail];
  rb->tail = (rb->tail + 1) % BUFFER_SIZE;
  return data;
}
    

This code adds data to and removes data from a fixed-size circular buffer using simple index updates.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single-step insert or remove at an index.
• How many times: Each call does exactly one insert or one remove operation.

How Execution Grows With Input

Each insert or remove takes the same small number of steps, no matter how full the buffer is.

Input Size (n)	Approx. Operations
10	1 operation per insert or remove
100	1 operation per insert or remove
1000	1 operation per insert or remove

Pattern observation: The time to insert or remove does not grow with the number of items; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means each insert or remove operation takes the same small amount of time, no matter how many items are in the buffer.

Common Mistake

[X] Wrong: "Adding more items makes the insert slower because the buffer is bigger."

[OK] Correct: The ring buffer uses fixed-size indexing and does not shift data, so each insert or remove is always quick and does not depend on buffer size.

Interview Connect

Understanding how ring buffers work and their time complexity shows you know how to handle fixed-size data efficiently, a useful skill in many real-world embedded systems.

Self-Check

"What if the ring buffer needed to resize dynamically when full? How would the time complexity change?"