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?"