I2C acknowledge and NACK behavior in Embedded C - Time & Space Complexity

Time Complexity: I2C acknowledge and NACK behavior

O(n)

Understanding Time Complexity

When working with I2C communication, it is important to understand how acknowledge (ACK) and not-acknowledge (NACK) signals affect the flow of data.

We want to see how the time taken changes as the number of bytes sent or received grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Send bytes over I2C and check ACK/NACK
for (int i = 0; i < length; i++) {
    I2C_SendByte(data[i]);
    if (!I2C_WaitAck()) {
        // NACK received, stop sending
        break;
    }
}

This code sends bytes one by one over I2C and stops if a NACK is received.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending each byte and waiting for ACK/NACK.
• How many times: Up to length times, but may stop early if NACK occurs.

How Execution Grows With Input

As the number of bytes to send increases, the number of send-and-wait steps grows roughly the same.

Input Size (length)	Approx. Operations
10	Up to 10 send-and-wait steps
100	Up to 100 send-and-wait steps
1000	Up to 1000 send-and-wait steps

Pattern observation: The time grows linearly with the number of bytes sent, unless a NACK stops the process early.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in direct proportion to the number of bytes sent over I2C.

Common Mistake

[X] Wrong: "The time to send data over I2C is always constant regardless of data size."

[OK] Correct: Each byte requires sending and waiting for an ACK or NACK, so more bytes mean more time.

Interview Connect

Understanding how communication protocols like I2C handle acknowledgments helps you reason about timing and reliability in embedded systems.

Self-Check

"What if the code always waits for an ACK but never stops on NACK? How would the time complexity change?"