W3C home > Mailing lists > Public > public-webapi@w3.org > February 2006

Re: Asymptotic computational complexity bounds for DOM methods

From: Bjoern Hoehrmann <derhoermi@gmx.net>
Date: Mon, 27 Feb 2006 09:15:36 +0100
To: Maciej Stachowiak <mjs@apple.com>
Cc: "Web APIs WG (public)" <public-webapi@w3.org>
Message-ID: <ovb502dhv59jlf7i6a3g3pg9cunofis4pq@hive.bjoern.hoehrmann.de>

* Maciej Stachowiak wrote:
>We should consider placing computational complexity bounds on DOM  
>methods in the future. For example, it would be perfectly legal to  
>make getElementById be O(N) in the number of elements in the  
>document, or even O(N^2). But in practice unless it is O(1) your  
>implementation will not be interoperable with web content, as there  
>will be web apps that will lock the user's machine for hours or even  
>days.

It does not matter whether your gEBI implementation is O(1) or O(N^2) if
your script engine is too slow in general, or if you are running on too
slow hardware, or if your implementations is limited to an environment
where gEBI is rarely, if ever, used, and so on. I see no reason to put
this information into the specifications (let alone as requirements).
-- 
Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
Weinh. Str. 22 · Telefon: +49(0)621/4309674 · http://www.bjoernsworld.de
68309 Mannheim · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/ 
Received on Monday, 27 February 2006 08:14:31 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:18:53 GMT