Why file systems organize persistent storage in Operating Systems - Performance Analysis

Time Complexity: Why file systems organize persistent storage

O(n)

Understanding Time Complexity

We want to understand how the time to access or manage files changes as the amount of stored data grows.

How does organizing storage affect the speed of finding and saving files?

Scenario Under Consideration

Analyze the time complexity of searching for a file in a simple file system structure.

// Pseudocode for searching a file in a directory
function findFile(directory, filename) {
  for (let file of directory.files) {
    if (file.name == filename) {
      return file;
    }
  }
  return null;
}
    

This code looks through all files in a directory one by one to find a match.

Identify Repeating Operations

Look for repeated steps that take time as input grows.

• Primary operation: Checking each file's name in the directory.
• How many times: Once for every file in the directory until the file is found or all files are checked.

How Execution Grows With Input

As the number of files increases, the time to find a file grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: Doubling the number of files roughly doubles the time to search.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a file grows directly with the number of files in the directory.

Common Mistake

[X] Wrong: "Searching a file always takes the same time no matter how many files there are."

[OK] Correct: The search checks files one by one, so more files mean more checks and more time.

Interview Connect

Understanding how file systems organize data helps you explain how computers manage storage efficiently as data grows.

Self-Check

What if the directory used an index or tree structure instead of a simple list? How would the time complexity change?