[net.unix] Why is dir search quadratic?

jeff@heurikon.UUCP (01/05/84)

I've seen numerous references to a directory search being "quadratic".
Could someone explain what this means, and why it is so?  All I can
figure out from those staements is that if the dir size is doubled, the
search time is quadrupled, but why?
				Dunka...
-- 
	Jeffrey Mattox, Heurikon Corp, Madison, WI
	{harpo, hao, philabs}!seismo!uwvax!heurikon!jeff  (news & mail)
		ihnp4!uwvax!heurikon!jeff  (mail)
	(Those paths are correct, despite what the headers might show.)

ka@hou3c.UUCP (Kenneth Almquist) (01/10/84)

The time to search a directory for a single file is roughly proportional
to the size of the directory.  What is quadratic is the time to access
all the files in a directory; if you double the number of files then there
are twice as many files to access and the access time for each file is
doubled, so the time to access all the files is quadrupled.
				Kenneth Almquist