**Subject:** Re: an in-kernel getcwd() implementation

**To:** Julian Assange *<proff@iq.org>*

**From:** Bill Sommerfeld *<sommerfeld@orchard.arlington.ma.us>*

**List:** tech-kern

**Date:** 03/07/1999 20:56:38
> > 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