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

>>For inserting:       O(n * log(n))
>>For retrieval:       O(n * log(n))
>>Total:               O(n * log(n) + n * log(n))
>>
>>
>>I can get:
>>
>>For inserting:       O(n)
>>For sorting *:       O(n * log(n))
>>For retrieval:       O(n)
>>Total:               O(2 * n + n * log(n))
>>
>>* No fancy algorithm, just quicksort.
>
> 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...
> 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.)
>
> BTW, if this comparison method worked, I could beat you both.  I have a
> balanced, fully-threaded 2-3 tree implementation with O(n log n) insertion
> and O(n) traversal.

(Referring to my previous reply):
Or, I could just prove that

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

=>

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


        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