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