What is the runtime of `Node.insertBefore`?

Question

I realize that each browser would implement it differently, but are there any references or benchmarks that specify this?

The simplest implementation would seem to be O(n) in the number of children of Node

EDIT: I ran some benchmarks. Here are the results

FireFox 3.6.10 on Linux

inserted 1000 elements into   1000 elements in  131.44 ms (average over 101 trials,  291.31 ms inc appendChild) while in dom: true
inserted 1000 elements into  10000 elements in  235.91 ms (average over  11 trials, 1311.36 ms inc appendChild) while in dom: true
inserted 1000 elements into 100000 elements in 2349.00 ms (average over  2 trials, 14150.50 ms inc appendChild) while in dom: true

inserted 1000 elements into   1000 elements in  13.13 ms (average over 101 trials,   267.00 ms inc appendChild) while in dom: false
inserted 1000 elements into  10000 elements in  67.45 ms (average over  11 trials,  1517.09 ms inc appendChild) while in dom: false
inserted 1000 elements into 100000 elements in 617.00 ms (average over   2 trials, 15214.50 ms inc appendChild) while in dom: false

Chrome 7 on Linux:

inserted  1000 elements into    1000 elements in      0.65 ms (average over   101 trials,     30.34 ms inc appendChild) while in dom: true
inserted  1000 elements into   10000 elements in      1.55 ms (average over    11 trials,    175.09 ms inc appendChild) while in dom: true
inserted  1000 elements into  100000 elements in     12.00 ms (average over     2 trials,   2255.00 ms inc appendChild) while in dom: true
inserted  1000 elements into    1000 elements in      0.49 ms (average over   101 trials,     41.13 ms inc appendChild) while in dom: false
inserted  1000 elements into   10000 elements in      1.36 ms (average over    11 trials,    301.18 ms inc appendChild) while in dom: false
inserted  1000 elements into  100000 elements in     12.00 ms (average over     2 trials,   2565.50 ms inc appendChild) while in dom: false

I created a dom Node, populated it with N elements, and then called insertBefore(newchild, randominitialchild) M times.

in dom: false means that the parent Node was not added to the document tree, so the browser should not be recalculating the layout (I hope?)

The results seem to show that inserting is O(n)

Answer 1

a.insertBefore(b)

If the nodes are stored in a linked list, then the process is as simple as finding the node before b which takes O(n) time because there are no backwards pointers, only next node pointers. We then change the next pointer of the node before b to a.

So yes, you are right, the process takes O(n) at best with a linked list, unless the list is doubly-linked.

Answer 2

I'd assume that the nodes are stored in a doubly-linked list, in which case insertBefore would take constant time. Singly-linked lists are rarely used in practical applications.

Answer 3

The time that is takes to actually add the node into the tree would be minimal. What's going to take time is to update and recalculate the layout.