On Fri, 08 Sep 2000 13:36:17 -0500, Thorsten Froehlich 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.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message