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