Re: Select a parrent node with s CSS selector?

  ----- Original Message ----- 
  From: Bruce Lawson 
  To: Andrew Fedoniouk ; Ilia Goranov ; www-style@w3.org 
  Sent: Monday, April 23, 2007 11:17 AM
  Subject: Re: Select a parrent node with s CSS selector?


    So to find style of p.description CSS engine will need to scan 
    1) all parents ( for body>div.content )  
    2) *and* all it is children ( for a:link )
     ...
    Your proposal changes the compelxity to O( n * n * m * d )  that is highly non-desirable as you may expect.

  Whilst I agree that it's far more complex to implement, does it mean that it's unimplementable and therefore beyond consideration?


This is not about complexity of implementation but about computational complexity of algorithm
needed to calculate such a selector:

See: http://en.wikipedia.org/wiki/Computational_complexity_theory

For example proposed selector

* < *:link  /* element that has at least one link inside */

requires deep scan of all children of any given element to verify the selector.  

Formula O( n * n ) means that document having twice more 
elements will require four times more time to match selectors.
(In practice this can be lot less - this is just a worst case - but still)

Again it is possible to compute this but selectors that have exponential  nature
are *highly* non-desirable.  

Andrew Fedoniouk.
http://terrainformatica.com