Start and stop conditions in Embedded C - Time & Space Complexity

Time Complexity: Start and stop conditions

O(n)

Understanding Time Complexity

We want to understand how the time a program takes changes when it uses start and stop conditions in loops.

How does the program's running time grow as the input or conditions change?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int i = 0;
while (i < n && !stop_condition()) {
    // do some work
    i++;
}

This code runs a loop that starts at zero and stops either when it reaches n or when a stop condition becomes true.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop running and checking conditions each time.
• How many times: Up to n times, but can stop earlier if stop_condition() is true.

How Execution Grows With Input

The loop can run fewer times if the stop condition happens early, or up to n times if it never triggers.

Input Size (n)	Approx. Operations
10	Up to 10 checks and work cycles
100	Up to 100 checks and work cycles
1000	Up to 1000 checks and work cycles

Pattern observation: The number of operations grows linearly with n, but can be less if the stop condition triggers early.

Final Time Complexity

Time Complexity: O(n)

This means the program's running time grows roughly in direct proportion to the input size n, unless it stops early.

Common Mistake

[X] Wrong: "The loop always runs exactly n times no matter what."

[OK] Correct: The loop can stop early if the stop condition becomes true, so it might run fewer times.

Interview Connect

Understanding how start and stop conditions affect loop time helps you explain how programs behave with different inputs and conditions.

Self-Check

"What if the stop condition is always false? How would the time complexity change?"

Practice

1.

What does a start condition indicate in embedded C communication protocols?

easy

A. It signals the beginning of data transmission.

B. It signals the end of data transmission.

C. It resets the device.

D. It pauses the communication temporarily.

Solution

1. Step 1: Understand start condition role

   The start condition marks when a device begins sending data on the communication line.

2. Step 2: Differentiate from stop condition

   Unlike the stop condition which ends communication, the start condition initiates it.

3. Final Answer:

   It signals the beginning of data transmission. -> Option A

4. Quick Check:

   Start condition = beginning signal [OK]

Hint: Start means begin communication, stop means end it [OK]

Common Mistakes:

• Confusing start with stop condition
• Thinking start resets the device
• Assuming start pauses communication

2.

Which of the following is the correct syntax to generate a stop condition in embedded C I2C communication?

void i2c_stop() {
    // Which line correctly generates stop condition?
    ?
}

easy

A. SDA = 1; SCL = 1;

B. SDA = 1; SCL = 0;

C. SDA = 0; SCL = 0;

D. SDA = 0; SCL = 1;

Solution

1. Step 1: Recall stop condition signal

   Stop condition occurs when SDA line goes from low to high while SCL is high.

2. Step 2: Match with code lines

   Setting SDA=1 and SCL=1 matches the stop condition signal.

3. Final Answer:

   SDA = 1; SCL = 1; -> Option A

4. Quick Check:

   Stop condition = SDA rising while SCL high [OK]

Hint: Stop condition: SDA rises while SCL is high [OK]

Common Mistakes:

• Setting SDA low instead of high for stop
• Setting SCL low during stop condition
• Confusing start and stop line states

3.

What will be the output of this code snippet simulating I2C start and stop conditions?

#include <stdio.h>
int start = 0, stop = 0;

void i2c_start() {
    start = 1;
    stop = 0;
}

void i2c_stop() {
    stop = 1;
    start = 0;
}

int main() {
    i2c_start();
    i2c_stop();
    if (start == 0 && stop == 1) {
        printf("Communication ended\n");
    } else {
        printf("Communication ongoing\n");
    }
    return 0;
}

medium

A. No output

B. Communication ongoing

C. Communication ended

D. Compilation error

Solution

1. Step 1: Trace function calls and variable changes

   Calling i2c_start() sets start=1, stop=0; then i2c_stop() sets stop=1, start=0.

2. Step 2: Evaluate if condition in main

   The condition start==0 and stop==1 is true, so it prints "Communication ended".

3. Final Answer:

   Communication ended -> Option C

4. Quick Check:

   start=0 & stop=1 means communication ended [OK]

Hint: Last called condition sets flags; check their final values [OK]

Common Mistakes:

• Assuming start remains 1 after stop call
• Confusing variable assignments order
• Expecting output before function calls

4.

Identify the error in this code snippet that tries to generate a start condition:

void i2c_start() {
    SDA = 1;
    SCL = 1;
    SDA = 0;
}

medium

A. SCL should be set to 0 after SDA goes low.

B. SCL should be low before SDA goes low to start communication.

C. SDA should go from low to high, not high to low.

D. SDA should go from high to low while SCL is high, so code is correct.

Solution

1. Step 1: Recall start condition definition

   Start condition requires SDA to go from high to low while SCL is high.

2. Step 2: Analyze code sequence

   The code first sets SDA=1, SCL=1 (establishing high-high state), then SDA=0 while SCL remains high, correctly generating the start condition.

3. Final Answer:

   SDA should go from high to low while SCL is high, so code is correct. -> Option D

4. Quick Check:

   Start condition = SDA high->low while SCL high [OK]

Hint: Start condition: SDA falls while SCL high [OK]

Common Mistakes:

• Confusing start (high->low) with stop (low->high)
• Thinking SCL must be low before SDA transition
• Ignoring that the code correctly times the transition

5.

You want to design a function that sends multiple data bytes over I2C with proper start and stop conditions. Which sequence correctly ensures communication integrity?

void send_data() {
    // Which sequence is correct?
    ?
}

hard

A. i2c_start(); send_byte(0x50); i2c_stop(); send_byte(0xA0);

B. i2c_start(); send_byte(0x50); send_byte(0xA0); i2c_stop();

C. send_byte(0x50); i2c_start(); send_byte(0xA0); i2c_stop();

D. i2c_stop(); send_byte(0x50); send_byte(0xA0); i2c_start();

Solution

1. Step 1: Understand I2C communication flow

   Communication must start with a start condition, then data bytes are sent, and finally a stop condition ends it.

2. Step 2: Evaluate each option sequence

   i2c_start(); send_byte(0x50); send_byte(0xA0); i2c_stop(); correctly starts communication, sends bytes, then stops. Others start or stop in wrong order.

3. Final Answer:

   i2c_start(); send_byte(0x50); send_byte(0xA0); i2c_stop(); -> Option B

4. Quick Check:

   Start -> data -> stop sequence is correct [OK]

Hint: Always start before sending data and stop after all bytes [OK]

Common Mistakes:

• Sending data before start condition
• Calling stop before all data sent
• Mixing order of start and stop calls