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).
