UART protocol fundamentals in Embedded C - Time & Space Complexity

Time Complexity: UART protocol fundamentals

O(n)

Understanding Time Complexity

When working with UART communication, 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 sending more bytes over UART.

Scenario Under Consideration

Analyze the time complexity of the following UART send function.

void uart_send_bytes(const uint8_t* data, size_t length) {
    for (size_t i = 0; i < length; i++) {
        while (!uart_tx_ready()) {
            // wait until UART is ready to send
        }
        uart_write_byte(data[i]);
    }
}
    

This code sends each byte one by one over UART, waiting for the transmitter to be ready before sending the next byte.

Identify Repeating Operations

Look at what repeats in this code.

• Primary operation: Sending each byte in the data array.
• How many times: Exactly once per byte, so it repeats length times.

How Execution Grows With Input

As you send more bytes, the time grows in a straight line with the number of bytes.

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: The time increases directly with the number of bytes sent.

Final Time Complexity

Time Complexity: O(n)

This means the time to send data grows linearly with the number of bytes you want to send.

Common Mistake

[X] Wrong: "Sending multiple bytes over UART takes the same time no matter how many bytes there are."

[OK] Correct: Each byte must be sent one after another, so more bytes mean more time spent waiting and sending.

Interview Connect

Understanding how UART sending time grows helps you design efficient communication in embedded systems and shows you can think about how code scales.

Self-Check

"What if we used DMA (Direct Memory Access) to send data instead of sending byte by byte? How would the time complexity change?"