> > It has to do with the use of per-process pointers into directories to
> > prevent a loop stat'ing every file in a directory from taking O(n**2)
> > time.  This can't help reverse lookups in any meaningful way.
> 
> O(n!), but still not nice.

O(n!) is a lot bigger than O(n**2).

(I think you confused + and * here)

the naive way of doing the directory scan looks at 1 dirent the first
time, 2 the second, 3 the third, etc., etc., for a total of n*(n+1)/2
entries.

The way I learned computational complexity, you drop all but the
highest-order term, so time proportional to n*(n+1)/2 collapses to
O(n**2).

					- Bill