Receiving a byte over UART in Embedded C - Time & Space Complexity

Time Complexity: Receiving a byte over UART

O(n)

Understanding Time Complexity

When receiving a byte over UART, it's important to understand how the time to get data changes as more data arrives.

We want to know how the program's waiting or processing time grows when receiving bytes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Wait until data is received
while (!(UART_STATUS_REG & DATA_READY_FLAG)) {
    // waiting
}
// Read the received byte
uint8_t received_byte = UART_DATA_REG;
    

This code waits for one byte to arrive on UART and then reads it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop checking the data ready flag repeatedly.
• How many times: It repeats until one byte arrives, which depends on the data arrival speed.

How Execution Grows With Input

Each byte requires waiting until it arrives, so time grows linearly with the number of bytes.

Input Size (n bytes)	Approx. Operations (wait loops)
10	About 10 times the wait for one byte
100	About 100 times the wait for one byte
1000	About 1000 times the wait for one byte

Pattern observation: The waiting time grows directly with the number of bytes received.

Final Time Complexity

Time Complexity: O(n)

This means the time to receive bytes grows in a straight line as more bytes come in.

Common Mistake

[X] Wrong: "Receiving one byte always takes the same fixed time regardless of data."

[OK] Correct: The code waits actively until data arrives, so if data is slow, waiting time grows and is not fixed.

Interview Connect

Understanding how waiting for hardware data scales helps you reason about program responsiveness and efficiency in embedded systems.

Self-Check

"What if we used an interrupt instead of polling the data ready flag? How would the time complexity change?"