|
![](/i/fill.gif) |
In article <slr### [at] fwi com> , ron### [at] povray org (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] trf de
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
![](/i/fill.gif) |