File input using ifstream in C++ - Time & Space Complexity

Time Complexity: File input using ifstream

O(n)

Understanding Time Complexity

When reading data from a file using ifstream, it's important to know how the time to read grows as the file size increases.

We want to understand how the program's running time changes when the file has more lines or data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <fstream>
#include <string>

void readFile(const std::string &filename) {
    std::ifstream file(filename);
    std::string line;
    while (std::getline(file, line)) {
        // Process each line (e.g., print or store)
    }
}
    

This code opens a file and reads it line by line until the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each line from the file inside the while loop.
• How many times: Once for every line in the file, until the file ends.

How Execution Grows With Input

As the number of lines in the file grows, the program reads more lines one by one.

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

Pattern observation: The number of operations grows directly with the number of lines in the file.

Final Time Complexity

Time Complexity: O(n)

This means the time to read the file grows in a straight line with the number of lines in the file.

Common Mistake

[X] Wrong: "Reading a file is always constant time because the file is on disk."

[OK] Correct: The program reads each line one by one, so more lines mean more work and more time.

Interview Connect

Understanding how file reading time grows helps you write efficient programs that handle large data smoothly.

Self-Check

"What if we read the file word by word instead of line by line? How would the time complexity change?"