Using scanf for input - Time & Space Complexity

Time Complexity: Using scanf for input

O(n)

Understanding Time Complexity

When we use scanf to get input in C, it takes some time to read the data. We want to understand how this reading time changes as we ask for more inputs.

How does the time to read inputs grow when we increase the number of inputs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
    }
    return 0;
}
    

This code reads an integer n and then reads n more integers from the user.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading an integer using scanf inside the loop.
• How many times: Exactly n times, where n is the number of inputs to read.

How Execution Grows With Input

Each time we increase n, we do one more input read. So the total reading time grows directly with n.

Input Size (n)	Approx. Operations
10	10 reads
100	100 reads
1000	1000 reads

Pattern observation: The time grows in a straight line as we add more inputs.

Final Time Complexity

Time Complexity: O(n)

This means the time to read inputs grows directly in proportion to how many inputs we read.

Common Mistake

[X] Wrong: "Reading inputs with scanf always takes the same time no matter how many inputs."

[OK] Correct: Each input requires a separate read operation, so more inputs mean more time spent reading.

Interview Connect

Understanding how input reading scales helps you reason about program speed and efficiency, a useful skill in many coding challenges and real projects.

Self-Check

"What if we read inputs using a single line with multiple values instead of one by one? How would the time complexity change?"