LATEX-L Archives

Mailing list for the LaTeX3 project


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
"J.Fine" <[log in to unmask]>
Reply To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Sat, 28 Nov 2009 17:25:39 +0000
text/plain (31 lines)
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.


The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).