On Thu, Aug 02, 2001 at 09:49:25AM +0200, Tollef Fog Heen wrote:
> * "David Starner"
> | music123 can be very slow, if you recurse into a large directory
> | with few music files. (It adds the files to a vector, but latter
> | removes them if they aren't recognized music files. O(N) behavior
> | to remove a file, and O(N) removals adds up to O(N^2) behavior.)
> No, it adds up to O(2N) == O(N).
It depends how it's implemented. A naive implementation could very easily
be O(N^2) (if you're removing k non-music-files, and each removal is O(n)
operations (like a memmove for an array deletion), eg)
For example:
int i;
for (i = n-1; i >= 0; i--) {
if (is_not_music(filename[i])) {
n--;
memmove(filename+i, filename+i+1, n-i);
}
}
will give you roughly O(nk) execution time. If you use a linked list, or you
ignore files by setting filename[i] = NULL, or similar, you'll have O(n) time
though.
Cheers,
aj
--
Anthony Towns <aj@humbug.org.au> <http://azure.humbug.org.au/~aj/>
I don't speak for anyone save myself. GPG signed mail preferred.
``_Any_ increase in interface difficulty, in exchange for a benefit you
do not understand, cannot perceive, or don't care about, is too much.''
-- John S. Novak, III (The Humblest Man on the Net)
Attachment:
pgp1sTeAav13X.pgp
Description: PGP signature