Sat, 28 Nov 2009 17:25:39 +0000
> 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.
The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).