|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |