Input capture mode in Embedded C - Time & Space Complexity

Time Complexity: Input capture mode

O(n)

Understanding Time Complexity

We want to understand how the time taken by input capture mode changes as the amount of input grows.

How does the program's work increase when it waits for and processes more input data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void capture_input(char *buffer, int max_length) {
    int i = 0;
    char c;
    while(i < max_length - 1) {
        c = getchar();
        if(c == '\n' || c == EOF) {
            break;
        }
        buffer[i++] = c;
    }
    buffer[i] = '\0';
}
    

This code reads characters one by one from input until it reaches the maximum length or a newline/end signal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop reading each character from input.
• How many times: Up to max_length - 1 times, depending on input.

How Execution Grows With Input

As the allowed input size grows, the program reads more characters one by one.

Input Size (max_length)	Approx. Operations (characters read)
10	Up to 9 characters
100	Up to 99 characters
1000	Up to 999 characters

Pattern observation: The number of operations grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to capture input grows linearly with the number of characters allowed.

Common Mistake

[X] Wrong: "The input capture always takes the same time no matter how much input is allowed."

[OK] Correct: The loop reads each character until it reaches the limit or newline, so more allowed input means more reads and more time.

Interview Connect

Understanding how input reading scales helps you explain how programs handle user data efficiently and respond quickly.

Self-Check

"What if we changed the input capture to stop only on a special character instead of max length? How would the time complexity change?"