# Re: Asymptotic computational complexity bounds for DOM methods

From: Maciej Stachowiak <mjs@apple.com>
Date: Mon, 27 Feb 2006 01:51:14 -0800
Message-Id: <75D73BBE-1BE9-44C5-AB49-E01BBB824981@apple.com>
Cc: "Web APIs WG (public)" <public-webapi@w3.org>
To: "L. David Baron" <dbaron@dbaron.org>
```

On Feb 27, 2006, at 1:15 AM, L. David Baron wrote:

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

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,
which is about 2x the 68 I get with ~1000. So that's evidence that it
is at least amortized constant time.

<div id="foo">
<span></span>
</div>
<script>
var foo = document.getElementById("foo");
var n = foo.firstChild;
var startTime = new Date();
while (n) {
n = n.nextSibling;
}
var endTime = new Date();
}
</script>

Similarly with this test I could not find any change in the timings
regardless of number of spans before the "nextToLast" span, even when
I added tens of thousands, which seems like evidence that it is in
fact constant time:

<div>
<span></span>
<span id="nextToLast"></span>
<span></span>
</div>

<script>
var n = document.getElementById("nextToLast")
var startTime = new Date();
n = n.nextSibling;
var endTime = new Date();