Lars wrote: == J.Fine skrev: > The quadratic running time may be poison. Once that feature is > there, users may use it heavily. > > It would be sensible to estimate the running time for a dictionary > with 100 keys. Note that even this implementation is strongly linear in the number of dictionary entries; to notice the quadratic term behaviour you'd rather have to consider a dictionary where all keys are 100 characters long -- and even then you might discover that linear terms dominate the complexity, since the inner loop of what contributes that quadratic term to the complexity is TeX grabbing tokens for a macro argument. == I don't see how key length comes into it. Suppose I start with an empty dictionary and add to it 100 entries, which are not known to be different. If determining if a dictionary already has a key is linear in the number of items in the dictionary, then the running time for building a dictionary of size n is at least order n^2. What's the cost of discovering if a dictionary has a key? I suspect that the best that can be done in any language is log n, while for TeX macros it is n. Thus, the cost of create a dictionary with n entries is of order n log n in most languages, and of order n^2 for TeX macros. Thank you for correcting my syntax for allocating fontdimen memory. -- Jonathan The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).