Subject: Re: an in-kernel getcwd() implementation
To: Julian Assange <firstname.lastname@example.org>
From: Bill Sommerfeld <email@example.com>
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