What is the time complexity of HTML DOM lookups
big-o, dom, html, javascript, time-complexity
Solution
`getElementById` can safely assumed to be `O(1)` in a modern browser as a hashtable is the perfect data structure for the id=>element mapping.
Without any optimizations any simply query - be it a css selector, an id lookup, a class or tag name lookup - is not worse than `O(n)` since one iteration over all elements is always enough.
However, in a good browser I'd expect it to have a tagname=>elements mapping, so `getElementsByTagName` would be `O(1)` too.
Problem
Assuming there are no crazy optimizations (I'm looking at you Chrome). I'm talking about raw, nasty, ain't-broke-don't-fix-it, ie v6 javascript, cost. The lower limit being: ``` document.getElementById() ``` Versus: ``` document.getElementsByTagName('div') lookup. ```