In article <39bab334@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> : How?  That is simple:  I read in the words. Then sort them and then just
> : count when retrieving.
>
>   But it uses more memory (specially if there are many repetitions).

Yes, it uses more memory, but in case you overlooked it, in one of my posts
I prove (using limits) that the worst case of your method will be slower for
a big enough n.
In case you start mentioning memory allocation time is not constant,
consider that I know the size of memory needed in advance, so I just need
one allocation for loading everything into memory!

> : Of course I can do this using the STL (see below)!  But your example shows
> : something dangerous you forgot:  the STL can trick you into thinking you
> : have found a good algorithm, but in fact yours is nearly log(n) times slower
> : than mine for most cases (for log(n) > 2)!
>
>   The O-notation doesn't know the term "log(n) times slower" if the speed
> is already at least O(log(n)).

Did I use big-O notation here?  I can't see it.  To repeat my other post
(also mentioned above):

 lim   2n lg n   >   lim   2n + n lg n
n->oo               n->oo

=>

 lim   n lg n  >   lim   2n
n->oo             n->oo


I agree that my language is not very good at explaining the speed
difference, but I think "nearly log(n) times slower" describes the above
very well!

>   My version and your version have both the same O value and there's a good
> reason for this in this case: Your version can be a lot slower when the
> input is very big and there's a lot of repetition (imagine that the input
> is "word1 word2 word1 word2..." millions of times). The speed is still
> O(n*log(n)) in relation with the size of the input, but the speed factor can
> vary a lot.

Yes, but as I mentioned before, my only mistake was adding them up in the
total and leaving the big-O around it.  I never said "O(n * log(n) + n *
log(n)) < O(2 * n + n * log(n))" or even "O(n * log(n)) < O(n * log(n))".

Just remove the big-O around the totals, and everything is correct!

I really should have cared more and we wouldn't have this argument about the
total big-O which has nothing to do with your implementation being slower
for a big enough n, which is all I wanted to show!!!

In fact you are falling in the same trap I fell at first when replying to
Ron:  Trying to compare these two functions based on big-O notation!  But
you simply cannot compare two functions with the same big-O with each other
using big-O.  Other methods are needed, i.e. limits will solve the problem
for the worst case very well.


      Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message