Thread-Topic: object type / instance arguments
Thread-Index: AcpwQkjJu+yDYf2OTy2qE7q0uU9RDQADFZOL
References: <19209.8773.325233.396932@morse.mittelbach-online.de>
            <4B0C694B.1080803@residenset.net>
            <4B0E8600.6000003@residenset.net>,<19215.63158.760427.5070@morse.mittelbach-online.de>
            <A969C9F865F27B428A8E60E39D3CED1522F5AAE763@KIELDERCMS1.open.ac.uk>,<4B11459C.4070305@residenset.net>
Accept-Language: en-US, en-GB
Content-Language: en-GB
acceptlanguage: en-US, en-GB
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Message-ID:  <A969C9F865F27B428A8E60E39D3CED1522F5AAE765@KIELDERCMS1.open.ac.uk>
Date:         Sat, 28 Nov 2009 17:25:39 +0000
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
Sender: Mailing list for the LaTeX3 project <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
From: "J.Fine" <J.Fine@OPEN.AC.UK>
Subject: Re: object type / instance arguments
To: LATEX-L@LISTSERV.UNI-HEIDELBERG.DE
In-Reply-To:  <4B11459C.4070305@residenset.net>
Precedence: list
Status: R

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