Reading input basics in Rust - Time & Space Complexity

Time Complexity: Reading input basics

O(n)

Understanding Time Complexity

When reading input in Rust, it's important to know how the time to read grows as the input gets bigger.

We want to see how the program's work changes when the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::io;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read line");
    println!("You typed: {}", input.trim());
}

This code reads one line of input from the user and then prints it back.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading characters from input until a newline is found.
• How many times: Once per character in the input line.

How Execution Grows With Input

As the input line gets longer, the program reads more characters one by one.

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

Pattern observation: The work grows directly with the number of characters typed.

Final Time Complexity

Time Complexity: O(n)

This means the time to read input grows linearly with the input size.

Common Mistake

[X] Wrong: "Reading input always takes the same time no matter how long it is."

[OK] Correct: The program reads each character one by one, so longer input means more work and more time.

Interview Connect

Understanding how input reading scales helps you write programs that handle user data efficiently and avoid surprises with slow input handling.

Self-Check

"What if we read multiple lines in a loop instead of just one? How would the time complexity change?"