Re: CVS update: subversion/subversion/client main.c

On Mon, Feb 05, 2001 at 02:06:20AM -0500, Greg Hudson wrote:
> > Ah... rereading your comment now that I've written the
> > formula. You're saying that formula converges on 2N, right? Ah. So
> > yes... O(N) memory. The copying is something like O(N log N)
> > though. Those first ten bytes get copied a bunch of times.
>
> The time taken is also O(n); after all, no piece of memory is written
> to or copied from more than once, so the time taken can't be more than
> a constant factor times the amount of memory used.

Hmm... Boy, it's been too long since I did combinatorial analysis :-)

It doesn't feel right... seems that there should be a log(N) in there
somewhere, but I see your point. If we've shown the memory is O(N), and we
touch each of those memory locations twice (write, then read for a copy),
then we have O(2N) (== O(N)) for memory copying.

Just did the mail on that series progression. memory is O(2 - 1/(2^i)). Heh

> > Back to your original point: can you think of a goo term for
> > describing the behavior? [that I can slap into that comment?]
>
> You're just trying to save a constant factor, so there's no special
> mathematical term. I think "suboptimal" is what you're hunting
> for. :)

*laf* ... yup. Seeing that it is only a constant factor, then you bet.

> (Although if the file is small, maybe we shouldn't be caring.)

In this case, I think they are. But we should be wary of algorithms like
this if the file might be large. (or numerous)

Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/