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.

Сложность с ошибками обозначена, но ладно.

Но тут не все так однозначно, вот ext4, например, https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Hash_Tree_Directories. Т.е. хэш таблица может быть и отключена. А до ext3 сложность была O(n) получается

В случае ext4 и листинга надо учесть и это

Аномальное поведение одной директории (комментарий)

Ext4 умеет на ходу увеличивать размер этих структур, но не умеет уменьшать. Поэтому если создать в директории много файлов, а потом удалить, она останется большой. При доступе к такой директории приходится читать эти фрагменты, которые ещё и оказываются разбросаны по диску там и сям. Это медленно.

Зависит от файловой системы. В современных файловых системах (XFS, BtrFS, ZFS, NTFS) имена хранятся в дереве (B+ Tree и т.п), в результате они получаются отсортированы и время доступа O(log(n)).

В старых и простых файловых системах (FAT, старые файловые системы UNIX) имена хранятся в неотсортированном массиве/списке и время поиска O(n).

Открытие файла, если пусть известен, не требует получения листинга всей директории, вроде как.

Чтобы темы не плодить

А интересно, если я создаю поток не через цпп стд либу (стд::тхред и смежное), а юзаю что-нибудь более низкоуровневое (pthread, например), то цпп стд библиотека будет ли должным образом проинициализирована для порожденного потока? Если нет, то какой std::init() можно вызвать? Я помню давние страшилки - если создаешь поток через винапи, то библиотека плюсовая невалидна из-за отсутствия должной инициализации. Странно, что мешает сделать инициализацию «автоматической» через static члены.

Нет, плодите. Здесь не увидят.