Time complexity for an OS to find a file/directory?

  • Thread starter kolleamm
  • Start date
325
28
What is the time complexity for an OS to find a file? Is it O(1) time?

Let's say for example, you had a billion files in a single folder, and you wanted to load a file into a string in your program, would the system find a specific file right away, or would there be a longer wait?

Let's assume an OS like Windows.
 
195
94
What is the time complexity for an OS to find a file? Is it O(1) time?

Let's say for example, you had a billion files in a single folder, and you wanted to load a file into a string in your program, would the system find a specific file right away, or would there be a longer wait?

Let's assume an OS like Windows.
Older OS (since Windows 2000 or NT 4) have the utility for files to be indexed, therefore time to find a file in indexed database is ~ln(N), which is slightly slower than O(0). The indexing is active by default and run fully automatically in Windows 7 or Windows 10, but is absent in Windows 8.
Most of Unix/Linux versions also use a sort of indexing/hashing of file tree.
 
325
28
Older OS (since Windows 2000 or NT 4) have the utility for files to be indexed, therefore time to find a file in indexed database is ~ln(N), which is slightly slower than O(0). The indexing is active by default and run fully automatically since Windows 7.
Do you mean O (log n)? Which would be the time complexity for a binary tree search.
 
325
28
Yes, exactly
Ah I see, and by indexing do you mean alpha numerical order? I'm guessing by the ascii values of the characters?
 
195
94
Ah I see, and by indexing do you mean alpha numerical order? I'm guessing by the ascii values of the characters?
As i know, indexing is done by hashing the filename, and then by searching binary tree of hashes. Because hashes are shorter than full-path filenames, (4 to 16 bytes), the search is faster. Of course, this way do not work for templates, only for exact file names.
 
325
28
As i know, indexing is done by hashing the filename, and then by searching binary tree of hashes. Because hashes are shorter than filenames, (4 to 16 bytes), the search is faster. Of course, this way do not work for templates, only for exact file names.
Wow I never knew, thanks for the info!
 

Tom.G

Science Advisor
2,511
1,346
Donald Knuth's "The Art and Science of Computer Programming, Volume 3"
"THE ART OF COMPUTER PROGRAMMING, Volume 3/Sorting and Searching" Donald Knuth, ADDISON-WESLEY PUBLISHING COMPANY, Reading, Massachusetts. 1973, ISBN 0-201-03803-X

There are later editions.

'The Bible.' Highly recommended!

Cheers,
Tom
 

harborsparrow

Gold Member
523
102
It's a huge text tree search. Lots of possible searches, and even if indexing, lots of ways to index (and keep an index updated). Worst case can be quite bad, especially if a file was just added and hasn't made it into the index yet, or if you are using regular expressions and there are a gazillion candidates for consideration.
 

Want to reply to this thread?

"Time complexity for an OS to find a file/directory?" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top