What Is The Time Complexity Of Html Dom Lookups

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: docum

Solution 1:

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.