On 28 Aug 2008, at 9:07 pm, Jules Bean wrote:
Insert for Data.Sequence is log(i) where i is the position of the insertion; clearly bounded by log(n). toList is O(n) and index is (at worst) log(i).

I think the corresponding operations with tries are log(n),

Let the key you want to insert have length L.
Then insertion into a trie is O(L), independent of the size of the collection.
If the "alphabet" the key's elements are drawn from is large,
you can use a Ternary Search Tree, and insertion is
then O(L.lg B) where B is the branching factor.
There are fast Trie construction algorithms which are linear
in the total size of the collection, \sum_{i=1}^{n}L_i.

The worst case for Data.Sequence is where keys mostly vary at
the end, in which case comparisons take O(L) time, and the
cost is O(L.lg n), where n is usually much bigger than B.

So, it's all in the constants, isn't it?

No.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to