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 11:02:17 +0100
To: Maciej Stachowiak <mjs@apple.com>
Cc: "Web APIs WG (public)" <public-webapi@w3.org>
Message-ID: <20060227100217.GA2335@ridley.dbaron.org>
On Monday 2006-02-27 01:51 -0800, Maciej Stachowiak wrote:
> On Feb 27, 2006, at 1:15 AM, L. David Baron wrote:
> >Mozilla's implementation of Node.nextSibling is O(N) in the number of
> >(prior) siblings of the element.
> 
> Are you sure? I tried this test, with varying numbers of spans in the  
> div. With an O(N) implementation of nextSibling, it should be taking O 
> (N^2) time in the number of spans, but the scaling seems to be linear  
> in Firefox 1.5 as expected. With ~2000 spans I get a time of 134,  

So my knowledge turns out to be a little out of date.  There are some
caching optimizations to make it faster in some cases:
  https://bugzilla.mozilla.org/show_bug.cgi?id=240884
I'm haven't looked at those in detail, though, so I'm not quite sure
what's needed to defeat them, but it's still O(N) for at least some use
cases.

Also, the coefficient for the O(N) term could be really small, since
searching an array is a very simple operation; I suggest trying bigger
numbers.

-David

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

Received on Monday, 27 February 2006 10:03:20 GMT

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