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

Re: Asymptotic computational complexity bounds for DOM methods

From: L. David Baron <dbaron@dbaron.org>
Date: Mon, 27 Feb 2006 10:15:16 +0100
To: "Web APIs WG (public)" <public-webapi@w3.org>
Message-ID: <20060227091516.GA1039@ridley.dbaron.org>
On Sunday 2006-02-26 15:07 -0800, Maciej Stachowiak wrote:
> These don't necessarily have to be the tightest possible bounds. For  
> example, requiring Node.nextSibling to be O(1) might limit  
> implementations too much and an upper bound of O(log N) might be  
> sufficient. Sometimes there are also information-theoretic limits to  

Mozilla's implementation of Node.nextSibling is O(N) in the number of
(prior) siblings of the element.

-David

-- 
L. David Baron                                <URL: http://dbaron.org/ >
           Technical Lead, Layout & CSS, Mozilla Corporation

Received on Monday, 27 February 2006 09:16:13 GMT

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