Serial protocol design in Raspberry Pi - Time & Space Complexity

Time Complexity: Serial protocol design

O(n)

Understanding Time Complexity

When designing a serial protocol, it's important to understand how the time to send data grows as the amount of data increases.

We want to know how the time needed changes when we send more bytes over the serial connection.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Send data byte-by-byte over serial
void sendData(uint8_t* data, int length) {
  for (int i = 0; i < length; i++) {
    while (!serialReady()) {
      // wait until serial is ready
    }
    serialSendByte(data[i]);
  }
}
    

This code sends each byte of data one at a time, waiting for the serial port to be ready before sending the next byte.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each byte in the data array.
• How many times: Exactly once per byte, so 'length' times.

How Execution Grows With Input

As the number of bytes to send increases, the total time grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 waits and sends
100	About 100 waits and sends
1000	About 1000 waits and sends

Pattern observation: Doubling the data doubles the total operations and time.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows directly in proportion to the number of bytes you want to send.

Common Mistake

[X] Wrong: "Waiting for the serial port to be ready is a fixed cost and does not affect time growth."

[OK] Correct: The wait happens for every byte sent, so it adds up and grows with the data size, affecting total time.

Interview Connect

Understanding how sending data byte-by-byte affects time helps you design efficient communication protocols and shows you can think about performance in real devices.

Self-Check

"What if we buffered multiple bytes and sent them all at once? How would the time complexity change?"