Computational complexity of CSS selectors, part II, Was: Selector for parent/predecessor?

(See previous discussion on "Computational complexity of CSS" originated by 
[1] )

Brief explanation:
task of finding (resolving) all styles of elements in some document using
some stylesheet has computational complexity [2] expressed by the formula:

O ( n * m * d )

n - number of elements in the DOM of the document
m - number of CSS selectors in style sheet.
d - depth of DOM tree ( if descendant combinators are used )

Problem of proposed parent/predecessor selectors is simple -
such selectors if they will be implemented (and used in some document)
will suddenly change this formula to

O ( n * n * m * d )

That is changing needed computational time in the order of
magnitude ( one more 'n' multiplier ) and will make such selectors
practically non-usable.

Yes, there are some optimizations/heuristics available [3] but
selectors of proposed type narrow that optimization field
proportionally - in the order of magnitude.

Andrew Fedoniouk.


Received on Tuesday, 22 August 2006 19:13:52 UTC