Why input and output are required in Rust - Performance Analysis

Time Complexity: Why input and output are required

O(n)

Understanding Time Complexity

When we write programs, we often take input and produce output. Understanding how the program's work grows with input size helps us see how efficient it is.

We want to know how the time to handle input and produce output changes as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn print_numbers(n: u32) {
    for i in 1..=n {
        println!("{}", i);
    }
}

fn main() {
    print_numbers(5);
}
    

This code prints numbers from 1 up to n. It takes input n and outputs each number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that prints each number.
• How many times: It runs exactly n times, once for each number from 1 to n.

How Execution Grows With Input

As n grows, the program prints more numbers, so it does more work.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: The work grows directly with n. Double n, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the program grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Printing output is free and does not affect time complexity."

[OK] Correct: Printing each item takes time, so more output means more work and longer run time.

Interview Connect

Understanding how input size affects both processing and output helps you explain program efficiency clearly and confidently.

Self-Check

"What if we changed the code to print only even numbers up to n? How would the time complexity change?"