In article <slr### [at] fwicom> , ron### [at] povrayorg (Ron
Parker) wrote:

> You seem to have a misconception about how O() notation works.  The total for
> the first case is O(n*log(n)) and the total for the second case is...

I know, but I don't care enough (especially as a full "prove" is rather
long) as all I want to point out is that a map will not perform better than
a slightly different and in plain C easier to write algorithm than the
RB-tree most likely used for the map.   As for the total, you are right that
I shouldn't just have copy and pasted it together assuming anybody would get
the idea I wanted to show.

> O(n*log(n)).  They might have different constant factors, but the
> determination of which is faster is entirely a matter of determining those
> constant factors (which depend on the constant factors in the component parts
> of the algorithm.)

Yes, I am aware the constants matter here when using a simple sorting method
(merge sort) as I suggested.

To make you happy, I could have written (for the worst cases):

Numbers following variables should be read as subscripts!


T1(n) = (c1 * n * log n + c2) + (c3 * n * log n + c4) =
        (c1 + c3) * n * log n + (c2 + c4)

T2(n) = (c5 * n + c6) + (c7 * n + c8) + (c9 * n * log n + c10) =
        (c5 + c7) * n + (c9 * n * log n) + (c6 + c8 + c10)

For a large enough n this will hold:

c2 + c4 < (c5 + c7) * log n

and

c6 + c8 + c10 < (c5 + c7) * log n


So, I simply eliminate c2, c4, c6, c8 and c10 (set them to one) and can get:

T1(n) = (c1 + c3) * n * log n

T2(n) = (c5 + c7) * n + (c9 * n * log n)

Lets further assume that c1 = c3:

T1(n) = 2 * c1 * n * log n

T2(n) = (c5 + c7) * n + (c9 * n * log n)


And now comes the tricky part because I have to show that (c1 + c3) > c9.  I
do not need to assume anything about c5 and c7 as n * log n > n for a big
enough n. this leaves:

T1(n) = 2 * c1 * n * log n

T2(n) = c9 * n * log n

I assume that for map a RB-tree is used and for list.sort a merge sort that
just flips the pointers of two strings.  In both cases the algorithms need
to perform n * log n string comparisons, so we can just not count those.

This leaves the recursive calls and the swap operation for the merge sort,
and the walking through the tree (twice).

I assume that the merge sort will be faster*, but if anybody is not happy
with this, for string sorting there are plenty of other algorithms out
there...

In conclusion it is without problems possible to outperform the map used in
this case, and this is all I wanted to point out.


     Thorsten


* I don't want to spend the time to show this now.


____________________________________________________
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