Subject: Re: an in-kernel getcwd() implementation
To: Julian Assange <>
From: Bill Sommerfeld <>
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

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

					- Bill