Noriyuki Soda <soda@sra.co.jp> writes:
> I think the needed memory depends on a directory size which has 
> maximum number of entries, and depends on depth of directory tree,
> but doesn't depend on whole size of directory tree. Since only
> one directory per hierarchical level is needed to output sorted
> tree. Isn't it?
> i.e. Total (in-core + on-disk) memory cost by sort command is
> O(total_file_number), but the cost by find command may be almost
> O(directory_depth).
> Although I haven't checked acutall sources.

Actually, yeah, if done right, it should be on average less than that
used by sort.

If you do the sorting all up front (i.e. sort the arguments, then sort
the elements of each dir you enter before acting on them, etc.), i
guess the total element storage requirements will actually be
O(directory tree depth * per-directory entry count).

as compared to sort, which would be, basically, O(directory count *
per-directory entry count), and directory tree depth will most often
log-base-something of directory count.

In the worst case, find will be the same, in the average case it
should be better.


cgd
-- 
Chris Demetriou - cgd@netbsd.org - http://www.netbsd.org/People/Pages/cgd.html
Disclaimer: Not speaking for NetBSD, just expressing my own opinion.