Re: Asymptotic computational complexity bounds for DOM methods

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