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.